Tree problems in depth

Building a tree back from its traversals

Given pre-order and in-order sequences, you can reconstruct the exact original tree — this works because pre-order's first element is always the root, and once you know the root, in-order tells you exactly which values belong in the left subtree (everything before the root) versus the right subtree (everything after it).

function buildTree(preorder, inorder) {
  if (preorder.length === 0) return null;

  const rootVal = preorder[0];
  const root = { val: rootVal, left: null, right: null };

  const splitIndex = inorder.indexOf(rootVal);
  const leftInorder = inorder.slice(0, splitIndex);
  const rightInorder = inorder.slice(splitIndex + 1);

  root.left = buildTree(preorder.slice(1, 1 + leftInorder.length), leftInorder);
  root.right = buildTree(preorder.slice(1 + leftInorder.length), rightInorder);

  return root;
}

Dry run: rebuilding the tree in the diagram above

Calls 2, 4 and 5 get an empty leftInorder and rightInorder, so both their recursive calls hit preorder.length === 0 and return null — that's the base case doing its job, turning each of those calls into a leaf. The result is exactly the tree in the figure: 3 with left child 9, and right child 20 whose own children are 15 and 7.

Building from traversals in O(n): an index map and a moving pointer

Look again at the code above and ask what each call costs. inorder.indexOf scans the array to find the root, and the two slice calls copy the pieces. Both are O(length of the piece), and on a skewed tree the pieces shrink by only one each time, so the total is O(n²). It works for a five-node example and is too slow for a long one. Two changes make it O(n), and neither changes the idea.

1. Look the root up in a map. Build a Map from each value to its index in the in-order array once, in O(n). Finding the split point is then O(1). This needs the values to be distinct, as the problem promises; with duplicates the root's position is ambiguous and the tree is not unique.
2. Never copy. Instead of slicing, describe each subtree by the inclusive range lo..hi of the in-order array that it owns. The pre-order array is never cut either: its next unused element is always the next root to place, so a single moving index preIndex is enough.

function buildTree(preorder, inorder) {
  const indexOf = new Map(inorder.map((value, i) => [value, i])); // one pass, O(1) lookups later
  let preIndex = 0;
  function build(lo, hi) { // lo..hi is the inclusive range of inorder this subtree owns
    if (lo > hi) return null;
    const rootVal = preorder[preIndex++];
    const root = new TreeNode(rootVal);
    const mid = indexOf.get(rootVal);
    root.left = build(lo, mid - 1); // left first: preorder lists the left subtree before the right
    root.right = build(mid + 1, hi);
    return root;
  }
  return build(0, inorder.length - 1);
}

The order of the two recursive calls is not a style choice. Pre-order lists a node, then the whole left subtree, then the whole right subtree, so after taking the root, the next values in line belong to the left subtree, and build must handle the left side first so that preIndex is in the right place when the right side starts.

Dry run: preorder [3, 9, 20, 15, 7], inorder [9, 3, 15, 20, 7]

A call with lo > hi is an empty range and returns null without consuming anything from preorder. The roots are taken in the order 3, 9, 20, 15, 7, which is exactly the pre-order array front to back. Each of the n nodes is created once and each lookup is O(1), so the time is O(n) and the space is O(n) for the map plus O(h) for the recursion.

The same idea from in-order and post-order

Post-order puts the root last. Read the array from the back: the last value is the root, and before it come the right subtree and then the left subtree. So the pointer starts at the end and moves left, and the right subtree has to be built first:

function buildTreeFromPost(inorder, postorder) {
  const indexOf = new Map(inorder.map((value, i) => [value, i]));
  let postIndex = postorder.length - 1; // the root is LAST in postorder
  function build(lo, hi) {
    if (lo > hi) return null;
    const rootVal = postorder[postIndex--];
    const root = new TreeNode(rootVal);
    const mid = indexOf.get(rootVal);
    root.right = build(mid + 1, hi); // reading backwards, the right subtree comes first
    root.left = build(lo, mid - 1);
    return root;
  }
  return build(0, inorder.length - 1);
}

Lowest Common Ancestor (LCA)

The LCA of two nodes is the deepest node that has both as descendants. On a plain binary tree, you find it by searching both subtrees and noticing where the paths to each target first "meet."

function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root; // p and q split across both sides — root is the LCA
  return left ?? right;            // both on one side — pass that answer up
}

On a BST specifically, you can skip the full search: compare both targets against the current node's value. If both are smaller, go left; if both are bigger, go right; the moment they split (or match the node), you've found the LCA in O(log n) instead of O(n) — the BST property does the pruning for you.

Checking if a tree is height-balanced

function isBalanced(root) {
  function check(node) {
    if (node === null) return 0; // height of an empty tree

    const leftHeight = check(node.left);
    if (leftHeight === -1) return -1; // already unbalanced below — stop early

    const rightHeight = check(node.right);
    if (rightHeight === -1) return -1;

    if (Math.abs(leftHeight - rightHeight) > 1) return -1; // -1 means "unbalanced"

    return 1 + Math.max(leftHeight, rightHeight);
  }
  return check(root) !== -1;
}

Validate BST — the trap almost everyone falls into first

// pass down a valid (min, max) RANGE, tightened at every step
function isValidBST(node, min = -Infinity, max = Infinity) {
  if (node === null) return true;
  if (node.val <= min || node.val >= max) return false;

  return (
    isValidBST(node.left, min, node.val) &&   // left subtree must stay BELOW node.val
    isValidBST(node.right, node.val, max)      // right subtree must stay ABOVE node.val
  );
}

An equally valid alternative: run an in-order traversal and check the output is strictly increasing — since in-order on a real BST always produces sorted output (from the Trees chapter), any violation of that proves it isn't one. Both approaches are O(n) time, O(h) space.

Diameter of a binary tree

The diameter is the length of the longest path between any two nodes — and that path doesn't have to pass through the root. The subtlety: the longest path through a given node is leftHeight + rightHeight, but the final answer is the maximum of that value across every node, not just the root.

function diameterOfBinaryTree(root) {
  let diameter = 0;

  function height(node) {
    if (node === null) return 0;
    const leftHeight = height(node.left);
    const rightHeight = height(node.right);

    diameter = Math.max(diameter, leftHeight + rightHeight); // update global answer at EVERY node

    return 1 + Math.max(leftHeight, rightHeight); // but only return height upward
  }

  height(root);
  return diameter;
}

This is the same shape as isBalanced above — a single post-order pass that computes a per-node value (height) while side-effecting a running global answer. That combination — "return one thing up the call stack, but also track a separate best-so-far as you go" — is worth recognizing as its own recurring template; it also solves Binary Tree Maximum Path Sum with the same shape (track the best path found anywhere, but only return the best single-branch extension upward, since a path can't fork twice).

Path problems: three different questions, three templates

"Path sum" is a family, not a single problem, and the key to each member is the exact definition of a path. Read these three carefully, because they look alike and need different code.

Path Sum II: list every root-to-leaf path with a given sum

This is backtracking on a tree. Keep one array, path, which always holds the nodes from the root to the current node. On arrival, push the node; on the way out, pop it. At a leaf, check the remaining sum and, on a match, record a copy of the path.

function pathSum(root, target) {
  const paths = [];
  const path = [];
  function visit(node, remaining) {
    if (node === null) return;
    path.push(node.val);
    remaining -= node.val;
    if (node.left === null && node.right === null && remaining === 0) paths.push([...path]); // copy: path keeps changing
    visit(node.left, remaining);
    visit(node.right, remaining);
    path.pop(); // undo this node's push before returning to the parent
  }
  visit(root, target);
  return paths;
}

On the tree 5 (4 (11 (7, 2)), 8 (13, 4 (5, 1))) with target 22 it returns [[5, 4, 11, 2], [5, 8, 4, 5]]. Visiting is O(n), and each copy costs the length of the path it records, so the total grows beyond O(n) when many long paths match. The extra space is O(h) for the path and the recursion, not counting the answer.

Maximum Path Sum: the full code

Here a path may start and end at any node and may bend once, at its highest node, so a path through a node is: the best downward branch on the left, the node, the best downward branch on the right. The diameter chapter section above has the same shape, with node values in place of edge counts, and two changes: values can be negative, so a branch with a negative gain is dropped by taking Math.max(0, …), and the answer starts at −Infinity because every node might be negative.

function maxPathSum(root) {
  let best = -Infinity;
  function gain(node) {
    if (node === null) return 0;
    const left = Math.max(0, gain(node.left)); // a negative branch is better left out
    const right = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + left + right); // a path that bends at this node
    return node.val + Math.max(left, right); // but only one branch can continue upward
  }
  gain(root);
  return best;
}

The tree is −10 with children 9 and 20, where 20 has children 15 and 7. The best path is 15 → 20 → 7 with sum 42, found at the node 20. The bend value is recorded but never returned: a parent may extend only one branch, because a path cannot fork twice. That "record one thing, return another" split is the whole problem. Time O(n), space O(h). Writing let best = 0 instead of −Infinity is the usual bug: a tree of all negative values would then report 0, a path that does not exist.

Path Sum III: count downward paths that sum to a target

Now a path starts at any node and goes down, ending anywhere. The brute force starts a fresh downward sum from every node, which is O(n·h): fine on a balanced tree and O(n²) on a chain. The better idea comes from arrays. A subarray sum is a difference of two prefix sums, and a downward path is a subarray of the root-to-node path. Walk down keeping the running prefix sum from the root. A path that ends at the current node and sums to target exists for every earlier prefix on the same root path that equals prefix − target. A map from prefix sum to how many times it occurs on the current path answers that in O(1).

function pathSumIII(root, target) {
  const seen = new Map([[0, 1]]); // prefix sum -> how many times it occurs on the current root path
  let count = 0;
  function visit(node, prefix) {
    if (node === null) return;
    const sum = prefix + node.val;
    count += seen.get(sum - target) || 0; // paths ending here that start just below an earlier prefix
    seen.set(sum, (seen.get(sum) || 0) + 1);
    visit(node.left, sum);
    visit(node.right, sum);
    seen.set(sum, seen.get(sum) - 1); // leaving this node: it is no longer on the path
  }
  visit(root, 0);
  return count;
}

Dry run: the tree 10 (5 (3 (3, −2), 2 (·, 1)), −3 (·, 11)), target 8

Three paths sum to 8. Three details carry the whole solution. The map starts with {0: 1}: the empty prefix before the root, so that a path that begins at the root is found. The count for sum is decremented on the way back up, because once you leave a node its prefix is no longer on the current root path; forget that and paths from one branch are matched with prefixes from another. And the lookup happens before this node's own prefix is added, otherwise a target of 0 would count the empty path. Time O(n). Space is O(h) for the recursion; the map as written keeps a zero-count entry for every prefix it has seen, so it can grow to O(n), and deleting a key when its count reaches 0 holds it to O(h).

Pair-returning recursion: House Robber III

Thieves have found a street shaped like a binary tree. Robbing a house triggers an alarm if a directly linked house, its parent or its child, was also robbed. Maximise the money. The first idea is the recursion that falls straight out of the statement: for each node either rob it, and then skip its children and continue at its four grandchildren, or skip it and take the best of its two subtrees.

function robSlow(node) {
  if (node === null) return 0;
  let withNode = node.val;
  if (node.left !== null) withNode += robSlow(node.left.left) + robSlow(node.left.right);
  if (node.right !== null) withNode += robSlow(node.right.left) + robSlow(node.right.right);
  return Math.max(withNode, robSlow(node.left) + robSlow(node.right));
}

This is correct and very slow, because a node is reached both as a child of its parent and as a grandchild of its grandparent, and each of those visits repeats the whole subtree below it. Counting calls on a chain of nodes shows the growth:

The count multiplies by roughly 120 every ten nodes, so the running time grows exponentially with the height. The remedy is to return two answers from each call instead of one: the best total if this node is robbed, and the best total if it is skipped. Then the parent has everything it needs from each child in a single visit.

function rob(root) {
  function visit(node) {
    if (node === null) return [0, 0];
    const [leftRob, leftSkip] = visit(node.left);
    const [rightRob, rightSkip] = visit(node.right);
    const robThis = node.val + leftSkip + rightSkip; // robbing this house forces both children to be skipped
    const skipThis = Math.max(leftRob, leftSkip) + Math.max(rightRob, rightSkip); // children are free to choose
    return [robThis, skipThis];
  }
  const [robRoot, skipRoot] = visit(root);
  return Math.max(robRoot, skipRoot);
}

Dry run: the tree 3 (2 (·, 3), 3 (·, 1))

The answer is max(7, 6) = 7: rob the root and the two grandchildren 3 and 1. Time is O(n) with one visit per node and O(h) space. A common wrong idea is to take every other level. On the tree above the odd levels give 2 + 3 = 5 and the even levels 3 + 3 + 1 = 7, which happens to be right, but on the chain 2, 1, 1, 2 both parities give 3 while robbing the two ends gives 4. The pair-return template, one value per decision state, is the same trick that dynamic programming uses on a line, applied to a tree.

Serialization — turning a tree into a string and back

Pre-order with explicit null markers is the standard approach. With the markers, one traversal is enough to rebuild the exact tree shape without a second traversal like the construction problem above (post-order or level-order with markers work too; in-order does not).

function serialize(root) {
  if (root === null) return "null";
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data) {
  const values = data.split(",");
  let i = 0;

  function build() {
    if (values[i] === "null") { i++; return null; }
    const node = { val: Number(values[i++]), left: null, right: null };
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

The null markers are what make one traversal enough — they tell the rebuilder exactly where each branch ends, instead of needing a second traversal to disambiguate the shape.

Serialization, two more forms: level order and the compact BST

The pre-order form above is the shortest to write. Two others come up as often, and each has a reason to exist.

Level order with null markers

This is the format the practice problems print: 1,2,3,#,#,4,5. It is breadth-first, so it can be produced and consumed with a queue and no recursion, which matters for very deep trees. Missing children are written as #, and trailing markers are trimmed since they carry no information.

function serializeLevel(root) {
  if (root === null) return "";
  const tokens = [];
  const queue = [root];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    if (node === null) {
      tokens.push("#");
      continue;
    }
    tokens.push(String(node.val));
    queue.push(node.left, node.right);
  }
  while (tokens[tokens.length - 1] === "#") tokens.pop(); // trailing markers carry no information
  return tokens.join(",");
}

function deserializeLevel(data) {
  if (data === "") return null;
  const tokens = data.split(",");
  const root = new TreeNode(Number(tokens[0]));
  const queue = [root];
  let head = 0;
  let i = 1;
  while (head < queue.length && i < tokens.length) {
    const node = queue[head++];
    if (i < tokens.length && tokens[i] !== "#") {
      node.left = new TreeNode(Number(tokens[i]));
      queue.push(node.left);
    }
    i++;
    if (i < tokens.length && tokens[i] !== "#") {
      node.right = new TreeNode(Number(tokens[i]));
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

The reader mirrors the writer: take the next node from a queue and read the next two tokens as its left and right child, enqueueing any that are real. That is the same loop that turned a level-order array into a tree in the trees chapter. Time and space are O(n). Writing a null for the children of a missing node would be harmless but wasteful, and the reader would then expect those tokens, so the writer and the reader must agree.

The compact form for a BST: no markers at all

A binary search tree does not need null markers, because the ordering already says where a value goes. Write the pre-order values only. To rebuild, read the values in order and give each recursive call a legal range: the same (lower, upper) idea used to validate a BST. The next value becomes the node if it fits the range; if not, it belongs to an ancestor's other side, so this subtree is finished.

function serializeBST(root) {
  const values = [];
  (function visit(node) {
    if (node === null) return;
    values.push(node.val); // pre-order, and no null markers at all
    visit(node.left);
    visit(node.right);
  })(root);
  return values.join(",");
}

function deserializeBST(data) {
  if (data === "") return null;
  const values = data.split(",").map(Number);
  let i = 0;
  function build(lower, upper) {
    if (i >= values.length) return null;
    const val = values[i];
    if (val <= lower || val >= upper) return null; // belongs to an ancestor's other side
    i++;
    const node = new TreeNode(val);
    node.left = build(lower, val);
    node.right = build(val, upper);
    return node;
  }
  return build(-Infinity, Infinity);
}

For the BST 5 (3 (2, 4), 8 (·, 9)) the string is 5,3,2,4,8,9. Rebuilding it, build(−∞, ∞) takes 5 and then asks for a left child with the range (−∞, 5): 3 fits, and so does 2 under it with the range (−∞, 3). The next value, 4, is too big for the ranges (−∞, 2) and (2, 3), so both of 2's children come out null; back at 3, the range (3, 5) accepts 4, and 4's two children both reject the 8. At the root, the range (5, ∞) accepts 8, and then 9 becomes 8's right child. The string is about half the length of the marker form, and the reader runs in O(n): every value is consumed once and each range check is O(1). It requires a valid BST with distinct values. A general tree has no such ordering, which is why it needs the markers.

Level by level: the BFS variants

The level-order loop from the trees chapter is a template with a slot in the middle, where each variant does something different with one whole level at once. Keeping the current level as an array of nodes makes every variant a few lines, and it avoids removing items from the front of an array. One small helper builds the next level:

function childrenOf(level) {
  const next = [];
  for (const node of level) {
    if (node.left !== null) next.push(node.left);
    if (node.right !== null) next.push(node.right);
  }
  return next;
}

Right side view, zigzag, and level averages

function rightSideView(root) {
  if (root === null) return [];
  const view = [];
  let level = [root];
  while (level.length > 0) {
    view.push(level[level.length - 1].val); // the last node of a level is the one seen from the right
    level = childrenOf(level);
  }
  return view;
}

function zigzagLevelOrder(root) {
  if (root === null) return [];
  const result = [];
  let level = [root];
  let leftToRight = true;
  while (level.length > 0) {
    const values = level.map((node) => node.val);
    result.push(leftToRight ? values : values.reverse()); // reverse the output row, never the nodes
    leftToRight = !leftToRight;
    level = childrenOf(level);
  }
  return result;
}

function averageOfLevels(root) {
  if (root === null) return [];
  const averages = [];
  let level = [root];
  while (level.length > 0) {
    let sum = 0;
    for (const node of level) sum += node.val;
    averages.push(sum / level.length);
    level = childrenOf(level);
  }
  return averages;
}

Right side view is "the last node of every level": from the right you see the rightmost node of each depth, even when it is a left child that is the only node at that depth. Zigzag reads levels alternately left to right and right to left. The right way to do it keeps the traversal order fixed and reverses only the row of values being reported. Reversing the node array itself would swap the order in which the next level is built, and the zigzag would drift. Level averages sum a level and divide by its length; sums of integers stay exact up to 2⁵³, so overflow is not a concern for ordinary inputs.

All three are O(n) time. The extra space is the widest level, which is up to about n/2 nodes for a perfect tree.

Next right pointers in O(1) space

Fill in each node's next pointer with the node on its right at the same level, or null for the last node of a level. A queue does it in O(n) space. The O(1)-space version uses the pointers it is creating: once a level is linked, it can be walked like a linked list, and that walk is the traversal for building the links of the level below. For a perfect binary tree (every node has either two children or none, all leaves at one depth), the links are easy to see:

function connectPerfect(root) {
  let leftmost = root;
  while (leftmost !== null && leftmost.left !== null) {
    for (let node = leftmost; node !== null; node = node.next) {
      node.left.next = node.right; // siblings under the same parent
      if (node.next !== null) node.right.next = node.next.left; // cousins across two parents
    }
    leftmost = leftmost.left; // the row below is already linked, so we can walk it next
  }
  return root;
}

Two kinds of link are made. Inside one parent, left.next = right. Across two parents, right.next = next.left, using the parent's own next pointer, which was set when the previous level was processed. That step is where the already-built links save the space. A general tree has missing children, so a node's neighbour may sit under a different parent entirely. The robust version walks one level as a linked list and uses a dummy node and a tail to string together the next level, which is the dummy-node trick from the linked lists chapter:

function connectAny(root) {
  let levelStart = root;
  while (levelStart !== null) {
    const dummy = new TreeNode(0);
    let tail = dummy;
    for (let node = levelStart; node !== null; node = node.next) {
      if (node.left !== null) {
        tail.next = node.left;
        tail = tail.next;
      }
      if (node.right !== null) {
        tail.next = node.right;
        tail = tail.next;
      }
    }
    levelStart = dummy.next; // the first node of the row we just linked
  }
  return root;
}

The loop over levelStart handles one level per pass, and the inner loop follows the next links of the level that is already linked. The first node of the level just built is dummy.next. The time is O(n) and the extra space O(1), and it also solves the perfect-tree case. The perfect-tree version is simpler to write when the problem promises that shape; reach for the general one when it does not.

Vertical order: giving every node a column

Draw the tree and slice it with vertical lines. A node's column is 0 for the root, one less for a left child and one more for a right child. A vertical order lists the values column by column from left to right. The row order inside a column is the part to pin down. A breadth-first traversal visits shallower nodes first and, within a row, left to right, so appending values to their column's list in visit order gives top-to-bottom, left-to-right inside each column:

function verticalOrder(root) {
  if (root === null) return [];
  const columns = new Map();
  let minCol = 0;
  let maxCol = 0;
  const queue = [[root, 0]];
  let head = 0;
  while (head < queue.length) {
    const [node, col] = queue[head++];
    if (!columns.has(col)) columns.set(col, []);
    columns.get(col).push(node.val);
    minCol = Math.min(minCol, col);
    maxCol = Math.max(maxCol, col);
    if (node.left !== null) queue.push([node.left, col - 1]);
    if (node.right !== null) queue.push([node.right, col + 1]);
  }
  const result = [];
  for (let col = minCol; col <= maxCol; col++) result.push(columns.get(col));
  return result;
}

The columns between the leftmost and the rightmost one are all occupied, because each column differs from its parent's by one, so the answer is read out by counting from minCol up to maxCol with no sorting. Time O(n), space O(n). For the tree 3 (9, 20 (15, 7)) the columns are 9 in −1; 3 and 15 in 0; 20 in 1; 7 in 2, giving [[9], [3, 15], [20], [7]].

function verticalTraversal(root) {
  const cells = [];
  (function visit(node, row, col) {
    if (node === null) return;
    cells.push([col, row, node.val]);
    visit(node.left, row + 1, col - 1);
    visit(node.right, row + 1, col + 1);
  })(root, 0, 0);
  cells.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]); // column, then row, then value
  const result = [];
  let lastCol = null;
  for (const [col, , val] of cells) {
    if (col !== lastCol) {
      result.push([]);
      lastCol = col;
    }
    result[result.length - 1].push(val);
  }
  return result;
}

On the tree 1 (2 (4, 6), 3 (5, 7)) the nodes 6 and 5 both sit at row 2 in column 0. The breadth-first version gives [1, 6, 5] for that column and the sorted version gives [1, 5, 6]. The sort makes the time O(n log n). Always read the statement for the tie rule before choosing between the two.

All nodes at distance K: the tree as a graph

Given the root, a target node and an integer k, return the values of every node whose distance from the target is exactly k edges. The trouble is that the nodes at that distance are not only below the target: they may be reached by going up first and then down another branch. Child pointers cannot go up.

The fix is the observation from the trees chapter: a tree is a graph, and a graph's distances come from breadth-first search. Add the missing edge, each node's parent, with one traversal that fills a map. Then run a breadth-first search from the target over three neighbours, left, right and parent, with a seen set so that the search does not walk back along the edge it just used. After exactly k rounds, the frontier is the answer.

function distanceK(root, target, k) {
  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);
      }
    }
  }

  const seen = new Set([target]); // a tree has no cycles, but the parent edge leads back where we came from
  let frontier = [target];
  for (let distance = 0; distance < k && frontier.length > 0; distance++) {
    const next = [];
    for (const node of frontier) {
      for (const neighbour of [node.left, node.right, parent.get(node)]) {
        if (neighbour !== null && !seen.has(neighbour)) {
          seen.add(neighbour);
          next.push(neighbour);
        }
      }
    }
    frontier = next;
  }
  return frontier.map((node) => node.val);
}

Dry run: tree 3 (5 (6, 2 (7, 4)), 1 (0, 8)), target 5, k = 2

The result is [7, 4, 1]. Notice that 1 is not under the target at all; only the parent edge finds it. Building the parent map is O(n), and the search visits each node at most once, so the time is O(n) and the space O(n). Without the seen set the search would step back across the edge it just used, so nodes would be reached again at the wrong distances. If k is larger than any distance, the frontier empties and the answer is []; k = 0 returns the target alone.

Kth smallest in a BST, and where its relatives live

In-order traversal of a BST is sorted (see the trees chapter), so the k-th smallest value is the k-th node an in-order walk visits. The iterative in-order from the trees chapter lets you stop in the middle of the walk:

function kthSmallest(root, k) {
  const stack = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    k--;
    if (k === 0) return node.val; // stop the moment the k-th value is visited
    node = node.right;
  }
  return undefined;
}

The walk goes down the left spine (at most the height h, pushing as it goes), then visits k nodes, popping and stepping right. It costs O(h + k) time and O(h) space, which is far less than O(n) when k is small. On the BST 5 (3 (2 (1, ·), 4), 6) the third smallest is 3: the visits are 1, 2, 3. If the tree is queried many times while it keeps changing, store each node's subtree size and descend by comparing k with the left size, which makes a query O(h) instead of O(h + k); that idea is developed in BST operations and ordered data.

The operations that exploit the ordering of a BST all live in that chapter, so they are not repeated here: insert and delete, in-order successor and predecessor, floor and ceiling, the BST iterator (the same stack idea, paused between calls), and building a height-balanced BST from a sorted array. This chapter stays with problems that are about the shape of a tree rather than its ordering.

Recognizing which of these four you need

• "Given two traversals, rebuild the tree" → construction (use pre/post-order for the root, in-order to split subtrees)
• "Find the common ancestor" → LCA (BST property prunes it to O(log n) if it's a BST)
• "Is this tree balanced/valid?" → compute the property bottom-up in one pass, short-circuit on failure
• "Save this tree to a file / send over a network" → serialize with pre-order + null markers

Recognising the rest of the problems in this chapter

The four questions above are the foundations. These phrases point to the longer techniques.