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.

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.

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