Introduction to Tree

What Is a Tree?

A tree is a recursive data structure: a single root node together with a set of child subtrees, each of which is itself a tree. Any two nodes are connected by exactly one path — there is no cycle, and no node has more than one parent. Equivalently, an n-node tree has exactly n−1 edges: a graph that is connected and acyclic satisfies |E| = |V| − 1, and it is precisely that edge budget that forces the unique root-to-node path — add any edge and you create a cycle, remove any and you disconnect it. A node's set of children can be of any size (it is not fixed at two), so this definition covers both a binary tree and a general n-ary tree such as a filesystem directory, an org chart, or a trie.

Because the definition allows any number of children per node, formulas that assume a fixed branching factor (for example, "each level holds twice as many nodes as the level above") only hold once that branching factor is fixed at 2 — they are not a property of trees in general. The height section further down makes this precise.

Recognizing the Pattern — and When Not To Use a Tree

Reach for a tree when data is naturally hierarchical: each item has exactly one parent, relationships form levels, and you need to walk up toward a root or down toward leaves (org charts, file systems, the DOM, category trees, decision trees). If an item can have more than one parent, or relationships can form a cycle, that is a general graph, not a tree — use graph traversal (BFS/DFS over an adjacency list) instead of tree recursion.

Looking hierarchical is not by itself a reason to use a tree. Weigh it against these named alternatives first:

• Hash map — if the only operation you need is "look up a node's value by key" and you do not care about ancestor or descendant relationships, a hash map gives O(1) average lookup versus a tree's O(h) walk. Use a tree only when the hierarchy itself — ancestors, depth, subtree ranges — is part of what you are querying.
• Flattened array + Euler tour / sparse table — if the hierarchy is built once and then queried many times for ancestor or lowest-common-ancestor (LCA) relationships, flatten the tree into an Euler tour and precompute a sparse table for O(1)-per-query LCA after O(n log n) preprocessing. This beats repeated O(h) pointer-chasing on a live tree when the shape is static and query volume is high.
• Union-Find (Disjoint Set Union) — if you need to merge whole hierarchies or repeatedly reparent nodes (dynamic connectivity rather than fixed ancestry), a tree's explicit parent pointers become expensive to rewire. Union-Find gives near-O(1) amortized union/find at the cost of losing explicit parent-child structure and ordered traversal.

If none of those pressures apply — the hierarchy changes over time, you need to walk up or down it, and per-query cost proportional to height is acceptable — a tree is the right choice.

Worked Example — the Data Every Claim Below Is Traced Against

Every correctness and complexity claim on this page is checked against this one concrete tree, given as a flat list of (id, parentId) rows — the same shape returned by a "list all rows" query on a self-referencing parentId column.

rows = [
  { id: 50, parentId: -1 },  // root: parentId === -1 marks "no parent"
  { id: 30, parentId: 50 },
  { id: 60, parentId: 50 },
  { id: 20, parentId: 30 },
  { id: 40, parentId: 30 },
  { id: 70, parentId: 60 },
  { id: 10, parentId: 20 },
]

Two invariants this data (and both approaches below) rely on, stated explicitly rather than assumed: (1) exactly one row has parentId === -1, marking the root sentinel; (2) every id is unique, and every non-root parentId refers to an id that also appears in rows. If either invariant is broken — a duplicate id, a dangling parentId, or a missing root — neither approach below is guaranteed to terminate or return a correct answer.

The diagram below is this exact tree. The task is to find all ancestors of node 20: following parentId from 20 gives 30, then from 30 gives 50, then 50's parentId is -1, so we stop. Read directly off the data, the correct answer is [30, 50] — the two approaches that follow are both traced against this same tree to confirm they reproduce it.

Approach 1 — Brute Force Over the Row List

Treat rows as an unindexed list and, for each hop toward the root, linearly scan it to find the row whose id matches the current node:

function ancestorsBruteForce(rows, targetId) {
  const result = [];
  let currentId = targetId;
  while (true) {
    const row = rows.find(r => r.id === currentId); // O(n) scan
    if (!row || row.parentId === -1) break;
    result.push(row.parentId);
    currentId = row.parentId;
  }
  return result;
}

Traced against the rows array above for targetId = 20:

1. Scan all 7 rows for id === 20 → found {id:20, parentId:30}. Push 30. result = [30].
2. Scan all 7 rows for id === 30 → found {id:30, parentId:50}. Push 50. result = [30, 50].
3. Scan all 7 rows for id === 50 → found {id:50, parentId:-1}. parentId === -1, stop.

Output: [30, 50] — matching the answer read directly off the data above (this relies on the two invariants stated earlier: unique ids and a single root sentinel, so rows.find always terminates on a real row). Each hop costs O(n) because .find scans the whole array; with h hops from node to root, total cost is O(n·h), which is O(n²) in the worst case where the tree is a single chain and h = n.

Approach 2 — Walking Parent Pointers on an Actual Tree

Build the tree once (map each id to a node object with a parent reference), then walk pointers directly — no scanning:

function buildTree(rows) {
  const nodes = new Map(rows.map(r => [r.id, { id: r.id, parent: null }]));
  for (const r of rows) {
    if (r.parentId !== -1) nodes.get(r.id).parent = nodes.get(r.parentId);
  }
  return nodes;
}

function ancestorsViaTree(nodes, targetId) {
  const result = [];
  let cur = nodes.get(targetId).parent; // O(1) pointer, not a scan
  while (cur) {
    result.push(cur.id);
    cur = cur.parent;
  }
  return result;
}

Traced for targetId = 20: nodes.get(20).parent is the node for 30 → push 30 → its .parent is the node for 50 → push 50 → its .parent is null → stop. Output: [30, 50], the same answer as the brute-force trace above — confirming both approaches are correct on this data, not just asserted to be.

The difference is cost per hop, not correctness: buildTree is a one-time O(n) pass, and after that every hop is O(1) because it follows a stored reference instead of searching. Total query cost is O(h), the height of the tree, versus brute force's O(n·h). On this 7-node example the gap is invisible; on a skewed tree with n = 100,000 nodes (h ≈ n), brute force does on the order of 10,000,000,000 comparisons while the pointer walk does at most 100,000.

Height: Why "Balanced" Alone Isn't Enough — You Need the Branching Factor

A common shortcut says a balanced tree with n nodes has height O(log n). That is only precise once the branching factor is fixed. For a binary tree specifically (branching factor 2), each level can hold at most twice as many nodes as the level above: level 0 holds 1, level 1 holds up to 2, level h holds up to 2^h. Summing a full binary tree of height h gives at most 2^h+1 − 1 nodes, so solving n ≤ 2^h+1 − 1 for the minimum achievable height gives:

h_min (binary tree, branching factor 2) = ⌈log₂(n + 1)⌉ − 1

This formula is specific to branching factor 2. A general tree — the kind defined at the top of this page, where a node can have any number of children — has minimum height governed by its actual branching factor b:

h_min (branching factor b) ≈ log_b(n)

This matters because a larger b gives a dramatically shorter tree for the same n. For n = 1,000,000 nodes: a binary tree needs h_min = ⌈log₂(1,000,001)⌉ − 1 = 19, while a tree with branching factor 100 (roughly a B-tree node's fan-out) needs only h_min ≈ log₁₀₀(1,000,000) = 3. This is exactly why B-trees (branching factor in the hundreds) and tries (branching factor 26 or 256) stay shallow even at large n — never apply the binary-tree height formula to a structure whose definition allows more than two children per node.

Sources: Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (3rd ed.), Ch. 10 (elementary tree data structures) and Ch. 12 (binary search trees) for the tree definition and the binary-tree height bound; Bender & Farach-Colton, "The LCA Problem Revisited" (2000), for the Euler tour + sparse table O(1)-per-query LCA technique; Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm" (1975), for Union-Find complexity. The worked example data, code, traces, and diagrams on this page are original to this revision.