Tree

In Turkish: Ağaç

Updated September 30, 20263 min read

In short

A tree is a hierarchical data structure made of nodes connected by edges, with a single root node at the top and child nodes branching out below it.

What is a tree data structure?

A tree organizes data as a hierarchy. It starts from a single root node, and every other node has exactly one parent and zero or more children. Nodes with no children are called leaves, and the number of edges on the longest path from the root down to a leaf is the tree's height. Because each node has only one parent, a tree never contains a cycle, which is a path that loops back to where it started.

A family tree or an organization chart is the everyday picture: one person at the top, with branches spreading downward. A common type is the binary tree, where each node has at most two children, called left and right. In a binary search tree (BST), every value in a node's left subtree is smaller than the node and every value in its right subtree is larger, so search, insert, and delete take O(log n) time when the tree is balanced. If values arrive in sorted order, a plain BST turns into a long chain and those operations degrade to O(n), which is why self-balancing variants such as AVL trees and red-black trees exist.

Trees are everywhere in software. The browser's DOM is a tree of HTML elements, file systems are trees of folders and files, compilers parse source code into an abstract syntax tree, and most relational database indexes use B-trees, wide and shallow trees designed to keep disk reads low. Heaps and tries (prefix trees used for autocomplete) are specialized trees too.

A tree is a special kind of graph: a connected graph with no cycles, in which n nodes are joined by exactly n - 1 edges. General graphs allow cycles and let any node connect to any other, so their traversal code needs extra bookkeeping to avoid visiting a node twice. Also note that a binary tree is not automatically a binary search tree; the BST is the version with the smaller-left, larger-right ordering rule.

Key takeaways

A tree has one root, and every other node has exactly one parent.
Nodes without children are called leaves.
A balanced binary search tree supports search, insert, and delete in O(log n) time; an unbalanced one can degrade to O(n).
Trees are traversed depth-first (preorder, inorder, or postorder) or breadth-first (level by level).
The DOM, file systems, and database indexes are all trees.

Example

Walking a folder tree with recursionjavascript

const root = {
  name: "src", // the root node
  children: [
    { name: "index.js", children: [] }, // a leaf: it has no children
    { name: "utils", children: [{ name: "math.js", children: [] }] },
  ],
};

// Depth-first traversal: print a node, then visit each of its children
function printTree(node, depth = 0) {
  console.log("  ".repeat(depth) + node.name);
  node.children.forEach((child) => printTree(child, depth + 1));
}

printTree(root); // src, index.js, utils, math.js (indented by depth)

Readers ask

What is the difference between a tree and a graph?

A tree is a restricted graph: it is connected, has no cycles, and has exactly one path between any two nodes. A graph can have cycles, disconnected parts, and any pattern of connections.

What is the difference between a binary tree and a binary search tree?

A binary tree only limits each node to at most two children. A binary search tree adds an ordering rule, smaller values on the left and larger values on the right, which makes fast searching possible.

What does it mean for a tree to be balanced?

A balanced tree keeps the subtrees of every node at similar heights, so the whole tree stays about log n levels tall. That guarantees O(log n) operations, while an unbalanced tree can grow n levels tall and behave like a linked list.