4.13.1 — Binary Trees, Search Trees & Traversals

A hash map gives you O(1) lookup and cannot answer a single ordered question. Ask it for the smallest key, or every key between "2026-01-01" and "2026-03-31", and it has nothing — the keys were deliberately scattered, so there is no order left to walk.

A tree keeps the order. It pays O(\log n) per lookup instead of O(1), and in exchange every ordered question becomes answerable. That trade is why both structures exist and why neither replaced the other.

1. The vocabulary, defined once

A tree is a set of nodes where each node has one parent, except one node called the root which has none, and there are no cycles. That is the whole definition, and the two clauses are what separate a tree from a general graph (Chapter 4.19).

Every node except the root has exactly one parent. A ==subtree== is any node together with everything below it, which is why tree algorithms are almost always recursive: the problem for the tree is the same problem for each subtree.

• Root — the top node.
• Leaf — a node with no children.
• Internal node — any node that is not a leaf.
• Depth of a node — how many edges from the root down to it. The root has depth 0.
• Height of a tree — the depth of its deepest node. A single node has height 0; an empty tree is conventionally −1.
• Subtree — a node plus everything under it. This is the recursive idea: the left child of the root is itself the root of a perfectly good tree.

A binary tree is a tree where every node has at most two children, called left and right. Left and right are part of the structure, not a drawing convention — a node with only a right child is a different tree from a node with only a left child, even though they have the same shape drawn as a blob.

Two shape words come up constantly:

• Complete — every level is full except possibly the last, which is filled from the left. This exact shape is what makes the array-based heap in Chapter 4.16 work.
• Balanced — every node's two subtrees differ in height by at most a small constant, so the height is O(\log n). This is the property that makes searching fast, and Chapter 4.13.2 is entirely about maintaining it.

class TreeNode {
  value: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;
  constructor(value: number) { this.value = value; }
}

That is the whole structure. Notice it is exactly the linked list node from Chapter 4.7 with a second pointer, which is a useful way to think about it: a tree is a linked structure that branches.

2. Binary tree versus binary search tree — the distinction people get wrong

This is asked in interviews specifically because the answer is often muddled.

A binary tree is a shape. There is no rule about what the values are. [5, 2, 9] arranged with 5 on top is a binary tree; so is [5, 9, 2].

A binary search tree (BST) is a binary tree plus an ordering rule:

For every node, every value in its left subtree is smaller, and every value in its right subtree is larger.

The word doing the work is every. The common wrong version of the rule is "the left child is smaller and the right child is larger", which is a strictly weaker statement, and it is wrong. Here is a tree that satisfies the wrong rule and is not a BST:

        20
       /  \
     10    30
          /  \
         5    40     ← 5 is in 20's RIGHT subtree, but 5 < 20

Every parent-child pair is fine: 10 < 20, 30 > 20, 5 < 30, 40 > 30. But 5 sits in 20's right subtree while being smaller than 20, so a search for 5 starting at the root would go right, never find it, and report absent. The BST property is about subtrees, not about children, and validating it is a standard interview question precisely because the naive check passes this tree.

The correct validation carries a permitted range downward:

function isValidBST(node: TreeNode | null,
                    min = -Infinity, max = Infinity): boolean {   // (1)
  if (node === null) return true;                                  // (2)
  if (node.value <= min || node.value >= max) return false;        // (3)
  return isValidBST(node.left,  min, node.value)                   // (4)
      && isValidBST(node.right, node.value, max);                  // (5)
}

1. Each call knows the open interval its value must fall inside. The root may be anything.
2. An empty subtree is trivially valid.
3. The actual check, against the inherited bounds rather than against a parent.
4. Going left, the ceiling tightens to this node's value — everything down there must be smaller than me.
5. Going right, the floor rises to this node's value. The bounds are what carry the "every descendant" part of the rule down the tree, and this is the whole idea of the algorithm.

On the broken tree above: at node 5 the call arrived with min = 20 (from going right at the root) and max = 30, and 5 <= 20 fails. Correctly rejected.

3. Search, insert, delete — and why delete has three cases

Search is a decision at each node: too big, go left; too small, go right; equal, found.

function search(root: TreeNode | null, target: number): TreeNode | null {
  let node = root;
  while (node !== null) {                       // (1)  iterative — O(1) space
    if (target === node.value) return node;
    node = target < node.value ? node.left : node.right;   // (2)
  }
  return null;                                  // (3)
}

1. Written as a loop rather than recursion, so it uses no stack space. Every BST operation on a path can be written this way.
2. One comparison discards an entire subtree. That is the source of the logarithmic cost: on a balanced tree each step halves the remaining candidates.
3. Falling off the bottom means it is not there.

Cost is O(h) where h is the height. Not O(\log n) — O(h). Those are equal only when the tree is balanced, and section 4 is about what happens when it is not.

Insert searches for where the value would be and puts a new leaf there. Same O(h).

Delete is the interesting one, because removing a node from the middle of a tree must leave a valid tree behind. There are three cases and they are worth knowing by name.

function deleteNode(root: TreeNode | null, target: number): TreeNode | null {
  if (root === null) return null;
  if (target < root.value) { root.left = deleteNode(root.left, target); return root; }   // (1)
  if (target > root.value) { root.right = deleteNode(root.right, target); return root; }

  // found it — three cases
  if (root.left === null) return root.right;    // (2)  no left child (covers the leaf case)
  if (root.right === null) return root.left;    // (3)  no right child

  let successor = root.right;                   // (4)
  while (successor.left !== null) successor = successor.left;
  root.value = successor.value;                 // (5)
  root.right = deleteNode(root.right, successor.value);   // (6)
  return root;
}

1. Navigate down, and rebuild the link on the way back up. Returning the (possibly new) subtree root and assigning it into the parent is the standard idiom that removes all the parent-pointer bookkeeping.
2. Case one and two, merged. If there is no left child, whatever is on the right takes this node's place. If the node was a leaf, root.right is also null and we return null, which correctly deletes it. Two cases, one line, because the leaf case is just the zero-children instance of "promote the only child".
3. Mirror image.
4. Case three: two children. You cannot promote either child, because each has its own subtree. The trick is to leave the node in place and change its value to one that is legal there. The only two values that work are the in-order predecessor (the largest value in the left subtree) or the in-order successor (the smallest in the right subtree). Here we take the successor: go right once, then left as far as possible.
5. Copy the successor's value up.
6. Now delete the successor from the right subtree. This recursion always terminates in case one or two, never back in case three, because the leftmost node of a subtree has no left child by construction.

Why the successor is the correct choice: it is the smallest value greater than everything on the left and smaller than everything else on the right, which is exactly the slot's requirement. Any other value would break the ordering rule somewhere.

4. The degeneration problem: why an unbalanced BST is a linked list

Insert 1, 2, 3, 4, 5 into an empty BST in that order. Every value is larger than everything already there, so every insert goes right:

1
 \
  2
   \
    3
     \
      4
       \
        5

The height is n−1. Search is O(n). You have built a linked list with extra memory overhead and worse cache behaviour. Every advantage is gone.

This is not a contrived case — it is the normal case, because real data arrives sorted far more often than random. Inserting users by ID, events by timestamp, or rows read out of a sorted file all produce exactly this.

The averages are worth knowing precisely:

• Randomly ordered insertions give an expected height of about 1.39 \log_2 n — close to optimal, which is why randomised structures work.
• Sorted insertions give height n — the worst possible.
• The gap between them is the entire justification for Chapter 4.13.2, which covers AVL and red-black trees. Those structures detect the imbalance as it forms and rotate the tree back into shape, guaranteeing O(\log n) height regardless of insertion order.

So the honest statement about BSTs is: a plain BST has O(h) operations, and h is only O(\log n) if something keeps it balanced. Saying "BST search is O(\log n)" without that qualification is the most common inaccuracy in this topic.

5. Traversals: four orders, and what each one is for

Visiting every node is O(n) whichever way you do it. The order is what makes each traversal useful.

function inorder(node: TreeNode | null, visit: (v: number) => void): void {
  if (node === null) return;
  inorder(node.left, visit);      // (1)  everything smaller, in order
  visit(node.value);              // (2)  me
  inorder(node.right, visit);     // (3)  everything larger, in order
}

The three traversal names all describe where the node itself is visited relative to its children:

• Pre-order — node, left, right. Visits a parent before its children.
• In-order — left, node, right. The code above.
• Post-order — left, right, node. Visits all children before the parent.

On the tree from the figure (50 at the root, 30 and 70 below, then 20, 40, 60, 80):

Traversal	Output	Use it for
pre-order	50 30 20 40 70 60 80	copying a tree, serialising
in-order	20 30 40 50 60 70 80	sorted output from a BST
post-order	20 40 30 60 80 70 50	freeing, computing a value from children
level-order	50 30 70 20 40 60 80	shortest path in edges, printing by layer

Each row deserves a sentence of why, because that is what makes them memorable rather than three arbitrary orders.

In-order on a BST prints sorted output. That falls straight out of the ordering rule: everything left is smaller, so visiting the left subtree first emits all smaller values, then this one, then the larger ones. This gives you a free correctness check — a tree is a valid BST if and only if its in-order traversal is strictly increasing, which is an alternative to the bounds algorithm in section 2 and is often the cleaner answer.

Pre-order copies and serialises. To rebuild a tree you must create a node before you can attach children to it, and pre-order hands you the parent first. Serialising pre-order with explicit null markers is the standard "serialise and deserialise a binary tree" answer.

Post-order computes upward. Any quantity defined in terms of a node's children — the height of a subtree, the sum of a subtree, whether a subtree is balanced, freeing memory in a manual-memory language — must have the children's answers before it can produce its own. That is post-order by definition.

function height(node: TreeNode | null): number {
  if (node === null) return -1;                                  // (1)
  return 1 + Math.max(height(node.left), height(node.right));    // (2)
}

1. The empty tree's height is −1 by convention, which makes a single leaf come out as 0 with no special case.
2. Both children must return before this line can run — the post-order shape, written as an expression rather than a visit.

Level-order needs a queue and is not recursive. It visits all of depth 0, then all of depth 1, and so on. This is breadth-first search on a tree, and Chapter 4.19 generalises it to graphs:

function levelOrder(root: TreeNode | null): number[][] {
  if (root === null) return [];
  const out: number[][] = [];
  let level: TreeNode[] = [root];                        // (1)
  while (level.length > 0) {
    out.push(level.map(n => n.value));                   // (2)
    const next: TreeNode[] = [];
    for (const node of level) {                          // (3)
      if (node.left) next.push(node.left);
      if (node.right) next.push(node.right);
    }
    level = next;                                        // (4)
  }
  return out;
}

1. Hold one whole level at a time rather than a single queue. This variant is worth knowing because it makes "group the output by level" free.
2. Emit this level.
3. Collect every child, left before right, which preserves left-to-right order in the next level.
4. Move down one level.

Time O(n), space O(w) where w is the widest level — which for a balanced tree is about n/2, so level-order uses more memory than depth-first traversal on wide trees, and less on deep skinny ones. That trade is the same one BFS and DFS make in Chapter 4.19.

6. Space, and the reason Morris traversal exists

Every recursive traversal costs O(h) stack space (Chapter 4.1 section 6). Balanced tree: O(\log n), negligible. Degenerate tree: O(n), and on a million-node chain your program crashes with a stack overflow before it finishes.

The iterative version with an explicit stack has the same O(h) space but no crash — it uses heap memory, which is far larger than the call stack (Chapter 2.5 covers why the stack is small and fixed while the heap grows).

function inorderIterative(root: TreeNode | null): number[] {
  const out: number[] = [], stack: TreeNode[] = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    while (node !== null) { stack.push(node); node = node.left; }  // (1)
    node = stack.pop()!;                                            // (2)
    out.push(node.value);
    node = node.right;                                              // (3)
  }
  return out;
}

1. Dive as far left as possible, remembering the path. This is the explicit version of what the recursive calls were doing implicitly.
2. The most recently pushed node is the leftmost unvisited one — that is the stack's ordering property (Chapter 4.7) doing the work.
3. Having visited it, its right subtree is next in in-order sequence.

There is a further step, Morris traversal, which achieves O(1) space by temporarily rewiring each node's rightmost descendant to point back at it, then undoing the rewiring on the way through. It is worth knowing it exists and that it exists for a reason — traversing a huge tree in an embedded system with a tiny stack — but it mutates the tree during traversal, which makes it unusable if anything else might read the tree concurrently.

What the interviewer will push on

"Define a binary search tree." The tell is whether you say subtree or child. "Left child smaller, right child larger" is the wrong answer, and the follow-up is to hand you the counterexample from section 2 and watch what you do with it.

"What is the time complexity of BST search?" O(h), and h is O(\log n) only if the tree is balanced. If you answer O(\log n) flatly, the follow-up is "what if I insert 1 through n in order?" and the honest answer is that it becomes a linked list at O(n).

"Delete a node with two children — which value replaces it, and why that one?" The in-order predecessor or successor, because those are the only two values that satisfy the ordering rule at that position. The deeper follow-up is why the recursive delete of the successor cannot recurse into the two-children case again: because the leftmost node of a subtree has no left child.

"How do you validate a BST?" Two correct answers: carry min and max bounds down, or check that the in-order traversal is strictly increasing. The wrong answer checks each node against its immediate children only. Volunteering both, and saying they are the same statement seen two ways, is the strong version.

"When would you use a BST over a hash map?" When you need order: minimum and maximum, predecessor and successor, range queries, or sorted iteration. A hash map cannot do any of those at all — not slowly, at all. That is why database indexes are trees and not hash tables (Chapter 7.3), even though a hash index would be faster for exact-match lookups, which is exactly what a hash index is used for when the database offers one.

One thing to volunteer: name the space complexity of your traversal without being asked, and say which tree shape makes it bad. "This recursion is O(h) stack space, so on a degenerate tree it is O(n) and could overflow — the iterative version has the same bound but uses heap memory." That sentence covers the two follow-ups they were about to ask.

Recall

• A binary tree is a shape; a BST adds the rule that every value in the left subtree is smaller and every value in the right is larger — subtrees, not children.
• BST search, insert and delete are O(h), and h = O(\log n) only if the tree is balanced; inserting sorted data gives h = n and a linked list.
• Deletion has three cases; with two children you copy in the in-order successor (leftmost node of the right subtree) and then delete that, which can never land in the two-children case again.
• In-order on a BST emits sorted values, which is also the cleanest validity check. Pre-order copies and serialises. Post-order computes anything defined from children upward. Level-order needs a queue and is BFS.
• Recursive traversal costs O(h) stack space; the explicit-stack version has the same bound but cannot overflow the call stack.

Self-test: Draw a tree where every parent-child pair satisfies the ordering rule but the tree is not a BST · Why does deleting the in-order successor never recurse into the two-children case? · Which traversal would you use to compute the height of every subtree, and why must it be that one? · What is the space complexity of level-order on a balanced tree versus a degenerate one? · Name three questions a BST answers that a hash map cannot answer at all.

Next: 4.13.2 fixes the degeneration problem — rotations, AVL's strict height rule, and the red-black tree that almost every language's ordered map is actually built from.