BST Algorithms And Lowest Common Ancestor

What's being tested

BST algorithms test whether you exploit ordering instead of treating the tree as an arbitrary binary tree. Expect recursive/iterative traversal, subtree aggregation, in-order ordering, range pruning, pointer rewiring, and sometimes lowest common ancestor via split-point logic.

Patterns & templates

• In-order traversal gives sorted order in a BST; use for convertBSTToDoublyList, validation, kth element, and sorted accumulation.

• Post-order aggregation returns (sum, count) or richer tuples from children; ideal for subtree-average checks in O(n) time.

• Range pruning for rangeSumBST(root, low, high) skips left when node.val < low and skips right when node.val > high.

• Iterative DFS stack avoids recursion-depth failures on skewed trees; same O(h) space average, O(n) worst-case.

• BST LCA split point: if both targets are less, go left; if both greater, go right; otherwise current node is LCA in O(h).

• Preorder BST construction uses bounds or a monotonic index; each value consumed once, O(n) time, O(h) recursion stack.

• In-place pointer threading for doubly list conversion tracks prev and head; carefully set left/right as prev/next.

Common pitfalls

Pitfall: Doing full traversal for range sum when BST ordering allows pruning; interviewers expect the optimized branch-skipping version.

Pitfall: Returning only a subtree sum for average checks; you need both sum and count, and integer division semantics must be clarified.

Pitfall: Forgetting skewed-tree behavior: recursion can hit O(n) depth, and “balanced tree” should not be assumed unless stated.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.