Trees

What makes something a tree

A tree is a linked structure with one rule a linked list doesn't have: each node can point to more than one child, and there are no cycles — you can never walk from a node back to itself. That single branching rule is what unlocks a completely different family of algorithms from the linear ones you just spent the beginner tier on.

Vocabulary you need cold

The BST property, drawn

This property is the entire reason BST search is O(log n) on a balanced tree — same idea as binary search on a sorted array, just implemented as pointers instead of index math: compare, then throw away half the tree.

function bstSearch(node, target) {
  if (node === null) return null;
  if (node.val === target) return node;
  return target < node.val
    ? bstSearch(node.left, target)
    : bstSearch(node.right, target);
}

The three depth-first traversal orders

All three visit every node exactly once and all three use the same recursive shape — the only difference is where you place the "visit this node" line relative to the two recursive calls.

function inOrder(node, out = []) {
  if (node === null) return out;
  inOrder(node.left, out);
  out.push(node.val);   // visit AFTER left, BEFORE right
  inOrder(node.right, out);
  return out;
}

function preOrder(node, out = []) {
  if (node === null) return out;
  out.push(node.val);   // visit FIRST
  preOrder(node.left, out);
  preOrder(node.right, out);
  return out;
}

function postOrder(node, out = []) {
  if (node === null) return out;
  postOrder(node.left, out);
  postOrder(node.right, out);
  out.push(node.val);   // visit LAST
  return out;
}

Breadth-first (level-order) — the one traversal that isn't depth-first

All three orders above dive to the bottom before coming back up. Level order does the opposite: visit every node at depth 0, then every node at depth 1, then depth 2 — this needs a queue, not recursion, because you have to remember an entire "frontier" of nodes at once.

function levelOrder(root) {
  if (root === null) return [];
  const result = [];
  const queue = [root];
  while (queue.length) {
    const levelSize = queue.length; // freeze how many belong to THIS level
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

The levelSize snapshot is the trick — without it you can't tell where one level ends and the next begins, since the queue just keeps growing as you go.

Dry run: level order on the tree from the first diagram

One row per pass through the outer while loop — that's what levelSize buys you: a clean boundary between levels instead of one row per node.

Queue is empty after iteration 3, so the while loop stops. Notice 10 enqueues only 14 — it has no left child, and the code's if (node.left) guard is what keeps a missing child from becoming a queued null.

Doing it without recursion — a near-guaranteed follow-up

"Can you do that iteratively?" is one of the most common tree follow-up questions, because it tests whether you actually understand what recursion was doing for you (managing a stack of "come back to this later" positions) rather than just pattern-matching the recursive shape.

// iterative pre-order — the easiest one: an explicit stack, push right before left
function preOrderIterative(root) {
  if (root === null) return [];
  const result = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.right) stack.push(node.right); // push right FIRST
    if (node.left) stack.push(node.left);   // so left gets popped first
  }
  return result;
}

// iterative in-order — trickier: walk left as far as possible, THEN visit, THEN go right
function inOrderIterative(root) {
  const result = [];
  const stack = [];
  let curr = root;
  while (curr !== null || stack.length) {
    while (curr !== null) {   // go as far left as possible, remembering the path
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();        // backtrack to the last unvisited node
    result.push(curr.val);
    curr = curr.right;         // then explore its right subtree
  }
  return result;
}

Post-order iteratively is the fiddly one — the cleanest trick is to compute pre-order but visiting right before left (swap the push order above), collect that into a list, then reverse it. Right-Node-Left reversed is exactly Left-Right-Node, which is post-order — worth remembering as a shortcut rather than deriving a true post-order stack machine from scratch under interview pressure.

The recursion template: base case, trust the children, combine

Most tree problems are one idea wearing different clothes, and learning to say that idea in three steps is worth more than memorising twenty solutions. A tree is defined recursively, a node whose children are themselves trees, so a function on a tree is best defined the same way. Write the function by answering three questions in order:

1. What does f(node) return, in one sentence, for the whole subtree rooted at node? Without this sentence the other two steps have no meaning.
2. What is f(null)? The base case is almost always the empty tree, and a correct base case makes the leaf case come out for free.
3. Assume f(node.left) and f(node.right) are already correct, and combine them with the node itself. That assumption is the "leap of faith" from the recursion chapter; you do not trace into the children, you use what the sentence in step 1 promises.

function maxDepth(root) {
  if (root === null) return 0; // an empty tree has no nodes
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

function isSameTree(p, q) {
  if (p === null && q === null) return true; // both ended together
  if (p === null || q === null) return false; // only one ended: the shapes differ
  return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

function isSymmetric(root) {
  function mirror(a, b) {
    if (a === null && b === null) return true;
    if (a === null || b === null) return false;
    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left); // outer with outer, inner with inner
  }
  return root === null || mirror(root.left, root.right);
}

function invertTree(root) {
  if (root === null) return null;
  const left = invertTree(root.left); // trust: these are already inverted
  const right = invertTree(root.right);
  root.left = right; // combine: swap the two inverted subtrees
  root.right = left;
  return root;
}

Check each function against the three questions. maxDepth(node) returns the number of nodes on the longest downward path from node; the empty tree has 0; and the node adds 1 to the deeper child. isSameTree(p, q) returns whether the two subtrees have the same shape and values; two empty trees are the same, one empty and one not is a mismatch, and otherwise the roots must match and both pairs of children must be the same. isSymmetric needs a helper, because a single tree cannot be compared with itself; the helper takes two nodes and pairs the outer children with each other and the inner children with each other. invertTree swaps two subtrees that are already inverted.

Dry run: isSymmetric on a tree and on a lopsided one

The symmetric tree has root 1 with two children 2, whose children are 3 and 4 on the left and 4 and 3 on the right. The calls are written in the order they are made, and ∅ stands for null.

Now take root 1 with two children 2, where each 2 has only a right child 3. The first call is mirror(2, 2); the values match, so it evaluates mirror(a.left, b.right), which is mirror(∅, 3). One side is empty and the other is not, so that call returns false and the && chain stops. Two such trees look alike in a drawing only if you forget that a mirror image flips the sides.

Recursion depth is a real limit. The call stack grows to the height of the tree. A tree with 100,000 nodes in a single chain makes the recursive maxDepth throw a RangeError in Node, because the calls nest 100,000 deep. A balanced tree is safe: its height is about log₂ n. If the input can be skewed and large, switch to a loop that handles one level at a time, which uses no recursion at all:

function maxDepthIterative(root) {
  if (root === null) return 0;
  let level = [root];
  let depth = 0;
  while (level.length > 0) {
    depth++;
    const next = [];
    for (const node of level) {
      if (node.left !== null) next.push(node.left);
      if (node.right !== null) next.push(node.right);
    }
    level = next;
  }
  return depth;
}

This returns 100000 on the same chain. It also touches every node once, so it is O(n) time, and its extra space is the widest level rather than the height.

Top-down versus bottom-up: which way does the information flow?

The template says "combine the children's answers", which is bottom-up: the information flows from the leaves toward the root through the return values. maxDepth above is bottom-up. There is a second style, top-down, where information flows from the root toward the leaves through the arguments, and the answer is accumulated on the way.

Look at the same problem both ways. Bottom-up, each node reports the height of its subtree. Top-down, each node is told its own depth, and a variable outside the function keeps the best depth seen:

function maxDepthTopDown(root) {
  let best = 0;
  function visit(node, depth) {
    if (node === null) return;
    best = Math.max(best, depth); // the information arrives from above
    visit(node.left, depth + 1);
    visit(node.right, depth + 1);
  }
  visit(root, 1);
  return best;
}

Both are correct and O(n). Which one you reach for depends on where the information a node needs comes from. If a node needs facts about its descendants (height, size, whether they are balanced), the answer travels up. If a node needs facts about its ancestors (my depth, the largest value above me, the sum of the path so far), the facts travel down as parameters.

Count good nodes: a top-down problem

A node is good if no node on the path from the root to it has a larger value. Whether a node is good depends only on its ancestors, so pass maxSoFar down and add up the good nodes on the way back.

function goodNodes(root) {
  function visit(node, maxSoFar) {
    if (node === null) return 0;
    const good = node.val >= maxSoFar ? 1 : 0; // nothing larger on the path from the root
    const nextMax = Math.max(maxSoFar, node.val);
    return good + visit(node.left, nextMax) + visit(node.right, nextMax);
  }
  return visit(root, -Infinity); // so the root itself always counts
}

The tree is 3 with children 1 and 4, where 1 has a left child 3, and 4 has children 1 and 5. Four nodes are good. Two details: the comparison is >=, not >, because "no larger node above" includes equal ones; and the starting value is −Infinity, so the root is good without a special case.

Minimum depth — the one-child trap

Minimum depth is the number of nodes on the shortest path from the root to a leaf. Copying maxDepth and swapping max for min looks right, and fails on the simplest input.

function minDepthWrong(root) {
  if (root === null) return 0;
  return 1 + Math.min(minDepthWrong(root.left), minDepthWrong(root.right));
}

Take a root 1 whose only child is a right child 2, whose only child is a right child 3. A node with one empty child has one side whose answer is 0, and Math.min happily picks it. The function returns 1 + min(0, …) = 1, but the root is not a leaf, so the shortest root-to-leaf path has 3 nodes. The empty side is not a path to a leaf at all. The fix is to treat a missing child as unavailable, and to fall back to the other side:

function minDepth(root) {
  if (root === null) return 0;
  if (root.left === null) return 1 + minDepth(root.right); // only one side exists: it must be used
  if (root.right === null) return 1 + minDepth(root.left);
  return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

There is also a level-by-level version. Breadth-first search visits nodes in order of depth, so the first leaf it meets is a nearest one, and it can stop right there:

function minDepthBFS(root) {
  if (root === null) return 0;
  let level = [root];
  let depth = 1;
  while (level.length > 0) {
    const next = [];
    for (const node of level) {
      if (node.left === null && node.right === null) return depth; // the first leaf found is a nearest leaf
      if (node.left !== null) next.push(node.left);
      if (node.right !== null) next.push(node.right);
    }
    level = next;
    depth++;
  }
  return depth;
}

Both are O(n) in the worst case. The recursive one always visits every node. The breadth-first one visits only the nodes above and on the shallowest leaf's level, so it can finish much earlier on a wide tree. The same stop-at-the-first-hit property is why shortest-path questions in unweighted graphs use breadth-first search.

Is one tree inside another? Subtree of another tree

Given root and subRoot, does some node of root have a subtree identical to subRoot? The recursion template gives it directly. The question about root is "does this tree contain subRoot?", and the answer is yes if the whole tree matches here, or if the left or right subtree contains it. "Match here" is exactly isSameTree, so the code reuses it.

function isSubtree(root, subRoot) {
  if (subRoot === null) return true;
  if (root === null) return false;
  return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

Cost. Each of the n nodes of root may start a comparison that walks up to m nodes of subRoot, so the time is O(n·m) in the worst case, for example a root that is a long run of equal values and a subtree that ends with one different value. The comparison stops at the first mismatch, which is why typical inputs are much faster. The space is O(h) for the recursion.

The O(n + m) version turns both trees into strings and asks whether one string contains the other, using a linear-time substring search such as KMP (see the string algorithms chapter). The encoding must be the pre-order serialization with null markers, and it has to be delimited:

function encode(node) {
  if (node === null) return ",#";
  return "," + node.val + encode(node.left) + encode(node.right); // every token starts with a comma
}

function isSubtreeByString(root, subRoot) {
  return encode(root).includes(encode(subRoot));
}

Flattening a tree into a linked list, in place

Flatten Binary Tree to Linked List asks you to rearrange the tree in place so that every node's left is null and its right points to the next node in pre-order. The result reads like a singly linked list built from the same nodes.

The first idea is to collect the nodes in pre-order into an array and relink them, which costs O(n) extra space. The second idea is a neat trick on the traversal order itself. Pre-order is node, left, right. Run it backwards and you get right, left, node. If you visit in that reversed order, then at the moment you visit a node, the node you visited just before it is exactly the node that comes next in pre-order. So keep a prev variable, and for every node set node.right = prev and node.left = null.

function flatten(root) {
  let prev = null;
  function visit(node) {
    if (node === null) return;
    visit(node.right); // reverse pre-order: right, left, node
    visit(node.left);
    node.right = prev; // prev is the node that comes NEXT in pre-order
    node.left = null;
    prev = node;
  }
  visit(root);
}

Dry run: flatten the tree 1 (left 2 with children 3 and 4, right 5 with a right child 6)

Read the chain from the root: 1 → 2 → 3 → 4 → 5 → 6, which is the pre-order of the original tree. The time is O(n); the extra space is the recursion stack, O(h).

If the interviewer asks for O(1) extra space, use the iterative version. For each node that has a left child, find the rightmost node of that left subtree (the last node of its pre-order), hang the node's old right subtree off it, and move the whole left subtree over to the right.

function flattenInPlace(root) {
  let node = root;
  while (node !== null) {
    if (node.left !== null) {
      let rightmost = node.left;
      while (rightmost.right !== null) rightmost = rightmost.right;
      rightmost.right = node.right; // the old right subtree follows the left subtree's last node
      node.right = node.left;
      node.left = null;
    }
    node = node.right;
  }
}

The inner walk looks like it could make the whole thing quadratic, but a node is on the walked spine of at most one ancestor's left subtree, so the walks add up to at most n steps and the total time is O(n). The space is O(1): no recursion, no stack. Linking the rightmost node of a left subtree to the node that must follow it, so that you can find your way on without a stack, is the same idea as the Morris traversal (which removes its temporary link again afterwards).

Trees that are not made of pointers: arrays and N-ary nodes

A complete tree stored in an array

A complete binary tree fills every level from left to right: all levels are full except possibly the last, and the last is packed to the left. That regular shape makes pointers unnecessary. Number the nodes in level order starting at 0, and the position alone gives the relationships:

const parentIndex = (i) => Math.floor((i - 1) / 2);
const leftIndex = (i) => 2 * i + 1;
const rightIndex = (i) => 2 * i + 2;

function treeFromCompleteArray(values, i = 0) {
  if (i >= values.length) return null;
  return new TreeNode(values[i], treeFromCompleteArray(values, leftIndex(i)), treeFromCompleteArray(values, rightIndex(i)));
}

This is how a heap is stored (see the heaps chapter) and why its operations never need to allocate a node. The layout is only efficient when the tree really is complete. A tree that is a single chain of right children needs the slot 2^(d+1) − 2 for the node at depth d: index 0, 2, 6, 14, 30 … so an array would be almost entirely empty and its length would double with every extra node.

function fromLevelOrder(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let head = 0;
  let i = 1;
  while (head < queue.length && i < values.length) {
    const node = queue[head++];
    if (i < values.length && values[i] !== null) {
      node.left = new TreeNode(values[i]);
      queue.push(node.left);
    }
    i++;
    if (i < values.length && values[i] !== null) {
      node.right = new TreeNode(values[i]);
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

The loop reads two array entries per node taken from the queue: first the left child, then the right, skipping null entries. That is the same order level-order traversal produces, which is why the format is called level order.

Checking that a tree is complete

A level-order walk can test completeness without computing a single index. Push every child, including empty ones. In a complete tree all real nodes come first; once you meet an empty slot, everything after it must be empty too. A real node after a gap means the last level is not packed to the left.

function isCompleteTree(root) {
  if (root === null) return true;
  const queue = [root];
  let head = 0;
  let seenGap = false;
  while (head < queue.length) {
    const node = queue[head++];
    if (node === null) {
      seenGap = true; // everything after the first gap must also be a gap
      continue;
    }
    if (seenGap) return false; // a real node after a gap: the last level is not packed to the left
    queue.push(node.left, node.right);
  }
  return true;
}

N-ary trees

Not every tree is binary. A file system, an HTML document and an organisation chart give each node any number of children. Store them as an array, children, and every binary template carries over with the two recursive calls replaced by a loop over the array:

class NaryNode {
  constructor(val, children = []) {
    this.val = val;
    this.children = children;
  }
}

function naryPreorder(node, out = []) {
  if (node === null) return out;
  out.push(node.val);
  for (const child of node.children) naryPreorder(child, out);
  return out;
}

function naryPostorder(node, out = []) {
  if (node === null) return out;
  for (const child of node.children) naryPostorder(child, out);
  out.push(node.val);
  return out;
}

function naryLevelOrder(root) {
  if (root === null) return [];
  const result = [];
  let level = [root];
  while (level.length > 0) {
    result.push(level.map((node) => node.val));
    level = level.flatMap((node) => node.children);
  }
  return result;
}

function naryMaxDepth(node) {
  if (node === null) return 0;
  let deepest = 0;
  for (const child of node.children) deepest = Math.max(deepest, naryMaxDepth(child));
  return 1 + deepest;
}

There is no standard in-order for an N-ary tree, since there is no single place "between" the children to visit the node; pre-order and post-order, which only depend on "before" and "after" the children, are the ones that exist. A leaf is a node whose children array is empty, and the recursion terminates there through the loop that runs zero times. The time for each traversal is O(n) and the space is O(h) for the recursion, or O(width) for the level-order version.

Parent pointers, and the tree as a graph

A tree node normally knows only its children, so questions that go up (ancestors, the path to the root, the nearest common ancestor) are awkward. Two fixes are standard. The first is to record each node's parent in a map, in one traversal:

function parentMap(root) {
  const parent = new Map([[root, null]]);
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    for (const child of [node.left, node.right]) {
      if (child !== null) {
        parent.set(child, node);
        stack.push(child);
      }
    }
  }
  return parent;
}

With the map, walking from any node to the root is a loop, and a question that needed a full search becomes a short walk. For example, the lowest common ancestor of two nodes is the first ancestor of one that is also an ancestor of the other:

function lcaByParents(parent, p, q) {
  const ancestorsOfP = new Set();
  for (let node = p; node !== null; node = parent.get(node)) ancestorsOfP.add(node);
  for (let node = q; node !== null; node = parent.get(node)) {
    if (ancestorsOfP.has(node)) return node; // the first ancestor of q that is also an ancestor of p
  }
  return null;
}

Building the map is O(n); each query afterwards is O(h) in time and space. The recursive LCA in the next chapter needs no map, only its O(h) recursion stack, so prefer it for a single query. The map pays off when you ask many questions about the same tree.

The second fix answers "is A an ancestor of B?" in O(1) after one traversal. Give every node an entry time when the traversal first reaches it and an exit time when it leaves, using one clock that ticks at both moments. Then A is an ancestor of B exactly when A's interval contains B's.

function entryExitTimes(root) {
  const tin = new Map();
  const tout = new Map();
  let clock = 0;
  function visit(node) {
    tin.set(node, clock++);
    if (node.left !== null) visit(node.left);
    if (node.right !== null) visit(node.right);
    tout.set(node, clock++);
  }
  visit(root);
  return { tin, tout };
}

function isAncestor(times, a, b) {
  return times.tin.get(a) <= times.tin.get(b) && times.tout.get(b) <= times.tout.get(a);
}

The intervals of two nodes are either nested (one is an ancestor of the other) or disjoint (neither is), and never partially overlapping, because a traversal finishes a subtree before it moves to the next one. This numbering is also how a subtree becomes a contiguous range of an array, which is how subtree queries are answered with a Fenwick or segment tree.

A tree is a graph. A tree with n nodes is connected, has no cycle and has exactly n − 1 edges. Once every node knows its parent as well as its children, each node has the neighbours { left, right, parent }, and any graph algorithm applies, in particular breadth-first search starting from any node, not only the root. That one observation solves a whole family ("every node at distance k from this node", "the longest path in the tree") which is worked in the tree problems chapter, and it connects this chapter to the graph chapters.

Complexity — the numbers to state out loud

Recognizing it in an unseen problem

• The input is described as a "binary tree" or "BST" with .left/.right
• "Sorted order" out of a BST → in-order is almost always the answer
• "Level by level" or "shortest path in an unweighted tree" → level order (BFS)
• "Build/copy/serialize" → pre-order; "safely delete/free" → post-order

Binary search trees have their own chapter

This chapter treats a BST as a binary tree with one extra property. The operations that use that property to be fast, namely insert, delete, successor and predecessor, floor and ceiling, the BST iterator, and building a balanced BST from a sorted array, are collected in BST operations and ordered data. Here you only need the search loop from earlier and the fact that an in-order walk of a BST is sorted.