Crux Read four small tree snippets — a traversal, a buggy BST validator, a recursive height function, and a tree-DP path sum — and predict the output or name the highest-leverage fix.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the sky
◷ 14 min
Tree bugs hide in the order of two recursive calls and in the difference between a local check and a global one. Read each snippet, run it in your head, and pick what a careful engineer would conclude or fix first.
Goal
Practise the core reading loop for tree code: predict a traversal’s exact output, spot the off-by-one-subtree bug in a BST validator, reason about the base case in recursive height, and recognise when a tree-DP return value must differ from the answer.
What exact sequence does this print, and what traversal is it?
Heads-up Pre-order would print node.value before recursing left. Here console.log sits between walk(node.left) and walk(node.right), so the left subtree is fully printed before the node — that is in-order, not pre-order.
Heads-up Post-order prints the node after both recursive calls. This code prints between the two calls, so 5 is not last. The order is in-order: 2, 3, 4, 5, 8, 9.
Heads-up Level-order needs a queue. This is recursion, which is depth-first, so it cannot produce a breadth-first level ordering.
Snippet 2 — the BST validator bug
function isBST(node) { if (node === null) return true; if (node.left && node.left.value >= node.value) return false; if (node.right && node.right.value <= node.value) return false; return isBST(node.left) && isBST(node.right);}// 5// / \// 3 8// /// 4 // 4 < 5, but sits in the RIGHT subtree of 5
Quiz
Completed
This validator returns true for the tree above, which is NOT a valid BST. What is the bug?
Heads-up The operator strictness only affects duplicate handling. The structural bug remains: a node can satisfy every parent-child check yet violate an ancestor's bound. You need a propagated (min, max) range.
Heads-up An in-order check is one correct fix, but the stated bug is specific: this code validates only local parent-child pairs. The range-bound method is the direct repair of that logic.
Heads-up An empty tree is a valid BST, so true is correct. Changing the base case would break correct trees and does nothing about the missing ancestor bound.
Snippet 3 — recursive height
function height(node) { if (node === null) return 0; // note: returns 0, not -1 return 1 + Math.max(height(node.left), height(node.right));}// single leaf nodeconsole.log(height(leaf));
Quiz
Completed
With the null base case returning 0, what does height(leaf) print, and what convention does that imply?
Heads-up The function adds 1 for the current node before returning, so a leaf returns 1 + max(0, 0) = 1, not 0. The 0 is what its null children return.
Heads-up This base case returns 0, not -1. -1 is the sentinel for edge-counted height; with 0 here you get node-counted height, and a leaf is 1.
Heads-up Math.max is called with two values: height(null) and height(null), each 0. No empty call occurs, so it returns 1 cleanly.
Snippet 4 — tree-DP path sum
function maxPathSum(root) { let best = -Infinity; function gain(node) { if (node === null) return 0; const left = Math.max(gain(node.left), 0); // drop negative branches const right = Math.max(gain(node.right), 0); best = Math.max(best, node.value + left + right); // path THROUGH node return node.value + Math.max(left, right); // path the parent can extend } gain(root); return best;}
Quiz
Completed
Why does gain() return node.value + max(left, right) while best is updated with node.value + left + right?
Heads-up If gain returned left + right, the parent would build a path that forks at this node and then forks again above — not a simple path. A path enters a node from one side only, so the upward return must use a single branch.
Heads-up The clamps only discard negative branches; they do not make the two formulas equal. Through-node (both branches) and upward-extendable (one branch) are genuinely different quantities.
Heads-up best must be a single shared accumulator across the whole traversal, which is exactly what the closure variable provides. Returning it from gain would conflate the local return value with the global answer — the bug the pattern avoids.
Recap
Reading tree code comes down to a few reflexes: locate the visit line relative to the two recursive calls to name the traversal (and remember in-order on a BST is sorted); never trust a BST validator that only checks parent-against-child — correctness needs a propagated (min, max) bound; read the null base case to know whether height is counted in nodes (return 0) or edges (return -1); and in tree DP, watch for the deliberate gap between what a node returns to its parent (one extendable branch) and what it contributes to the global answer (the full bend through it).