Trees and binary search trees

Why it matters

Trees are recursive by construction, which makes them a natural place to practice "solve the children, then combine". They also model real systems: file systems, DOM trees, syntax trees, and the ordered indexes behind databases and library maps. Interviewers use tree problems to check recursion fluency, the choice between depth-first and breadth-first traversal, and whether you respect an invariant such as BST ordering.

Core ideas

Pattern: Tree DFS / recursion on subtrees. Most tree problems are a post-order computation: get a result from each subtree and combine it at the node. Write the contract precisely, including the empty tree. For Diameter of Binary Tree the function returns the height of its subtree and, along the way, updates a global best with left_height + right_height. The returned value (one downward branch) and the recorded value (a path through the node) are different quantities, which is the key idea in Diameter and in Binary Tree Maximum Path Sum. Lowest Common Ancestor has the same shape: each call reports whether its subtree contains p or q, and the answer is the deepest node whose subtree, counting the node itself, contains both.

Traversal orders. Pre-order (node, left, right) copies or serializes structure; in-order (left, node, right) visits a BST in sorted order; post-order (left, right, node) computes results bottom-up. Iterative versions use an explicit stack, which avoids recursion limits on degenerate trees whose depth is n.

Pattern: Tree BFS / level order. A queue processes nodes by depth. To handle one level at a time, read the queue's length at the start of the level and pop exactly that many nodes. Right-side views, level averages, zigzag order and minimum depth are small changes to this loop.

Pattern: BST ordering invariant. Every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. This constrains whole subtrees, not just children, so validate it by passing an allowed interval (low, high) down the recursion, tightening high when going left and low when going right. Consequences:

• Search and insertion follow one root-to-leaf path: O(h) for height h.
• In-order traversal yields sorted keys, so the k-th smallest key is the k-th node visited; an iterator with an explicit stack uses O(h) memory and amortized O(1) per step.
• Deletion has three cases: a leaf is removed, a node with one child is spliced out, and a node with two children takes the key of its in-order successor (the leftmost node of its right subtree), which is then deleted.
• LCA in a BST walks down from the root: go left while both keys are smaller, right while both are larger, and stop otherwise.

Height and balance. Every BST bound is O(h), and inserting sorted keys into a plain BST produces a path with h = n. Self-balancing trees keep h = O(log n) with rotations: AVL trees bound the height difference between siblings, red-black trees enforce coloring rules. You rarely implement them in an interview, but you should explain why they exist and reach for the library ordered map (C++ std::map, Java TreeMap) when you need floor or ceiling queries. Storing subtree sizes in nodes supports rank and select in O(h).

Reconstruction. Pre-order plus in-order traversals determine a tree with distinct keys: the first pre-order element is the root, and its position in the in-order sequence splits left from right; an index map makes this O(n). Serialization needs explicit null markers to be unambiguous.

Common misconceptions

• "Check that each node lies between its children." The invariant concerns whole subtrees; a node deep in the left subtree can violate the root's bound.
• "BST operations are O(log n)." They are O(h); only balanced trees guarantee O(log n).
• "Tree recursion uses O(log n) stack." Only for balanced trees; a skewed tree needs O(n).
• "Return the global answer from every call." The value a call returns and the answer it records are often different.
• "BFS and DFS are interchangeable." BFS reaches the shallowest nodes first and organizes work by level; DFS suits subtree summaries and uses memory proportional to height rather than width.

How to approach it

State the function's contract and its value for an empty subtree before coding. Decide whether the question is about levels (BFS) or subtree summaries (DFS). For BSTs, name the invariant and use it to prune. Test an empty tree, a single node and a skewed tree. Interviewers typically probe the difference between returned and recorded values, BST validation and complexity on unbalanced input; deeper discussions cover balancing and when an ordered map from the standard library is the right tool. Aim to recognize these shapes in unseen problems rather than recall solutions to specific ones.