BST Practice Problems

How to Use This Problem List

BST problems require a different thinking mode than general binary tree problems. The BST property — left < root < right — is the key tool. Before writing any code, ask:

THINKING MODE for BST problems:
  ✓ Can I use the BST property to eliminate half the tree at each step?
     → O(h) solution exists (search, floor, ceil, LCA)
  ✓ Does the answer need sorted order?
     → Inorder traversal gives sorted sequence
  ✓ Does the answer need reverse sorted order?
     → Reverse inorder (Right → Root → Left)
  ✓ Do I need to count or accumulate across all nodes?
     → Full traversal O(n) — but can pruning reduce it?
  ✓ Is the structure of the tree the answer?
     → Construction / transformation problem

If BST property eliminates subtrees: O(h).
If you must visit every node: O(n).
The difference between O(log n) and O(n) is whether you exploit the BST property.

Pattern 1: BST Property Traversal — O(h) Operations

Use the BST ordering rule to navigate directly to the answer without visiting all nodes. Each step eliminates an entire subtree.

Complexity target: O(h) time, O(1) or O(h) space.

Recognition signal: "find value", "search", "insert", "delete", "closest", "floor", "ceiling", "LCA in BST". Any problem where the BST ordering property can guide your path — you don't need to visit all nodes.

Pattern 2: Inorder Traversal — Sorted Output

Inorder traversal produces nodes in ascending order. These problems exploit that sorted property.

Complexity target: O(n) time for full traversal, O(k) to stop at k-th element.

Recognition signal: "kth smallest", "sorted order", "validate", "successor", "predecessor", "iterator", "merge". The answer requires the BST's elements in sorted order or needs to compare adjacent values in sorted order.

Pattern 3: Reverse Inorder — Descending Order

Traverse Right → Root → Left to visit nodes in descending order. Used for kth largest and problems that accumulate from larger to smaller values.

Complexity target: O(n) or O(k) if stopping early.

Recognition signal: "kth largest", "greater than k", "descending order", "sum of nodes greater than", "max". The answer processes nodes from largest to smallest.

Pattern 4: Range Queries

Find, count, or sum elements within a value range [lo, hi]. The BST property allows pruning: skip entire subtrees known to be outside the range.

Complexity target: O(k + h) where k = number of values in range, h = tree height.

Recognition signal: "range [lo, hi]", "between lo and hi", "sum in range", "count in range", "trim", "within bounds". The problem restricts to a value interval.

Pattern 5: BST Construction and Transformation

Build a BST from given data or restructure an existing BST. Often involves exploiting sorted order or the BST property to avoid O(n²) naive approaches.

Complexity target: O(n) or O(n log n) depending on approach.

Recognition signal: "construct BST", "convert to BST", "balanced BST", "recover", "serialize", "how many unique BSTs". The problem creates or restructures a BST.

Pattern 6: Multi-BST and Advanced

Problems involving multiple BSTs, auxiliary data structures, or combining BST properties with other techniques.

Complexity target: O(n) for single-pass, O(h) for property-based navigation.

Recognition signal: "distance k from node", "in any direction", "largest BST subtree", "pairs", "count with property". These combine BST with graph-like traversal or additional data structures.

Recommended Study Order

Week 1 — BST Fundamentals
  Pattern 1 (Property):   Search, Insert, Delete, LCA of BST, Closest Value
  Pattern 2 (Inorder):    Validate BST, Kth Smallest, Inorder Successor

Week 2 — Traversal Mastery
  Pattern 3 (Reverse):    Kth Largest, Greater Sum Tree
  Pattern 4 (Range):      Range Sum of BST, Trim BST
  Pattern 2 (Iterator):   BST Iterator

Week 3 — Construction
  Pattern 5 (Build):      Sorted Array to BST, Recover BST, Serialize BST
  Pattern 5 (Advanced):   Build from Preorder, Balance a BST

Week 4 — Hard and Multi-BST
  Pattern 6 (Multi):      All Nodes at Distance K, Largest BST Subtree
  Pattern 5 (Hard):       Merge Two BSTs, Generate All Unique BSTs
  Mixed review of all patterns

Problem-Solving Checklist for BST Problems

1. CAN THE BST PROPERTY ELIMINATE SUBTREES?
   □ At each node, can you decide left or right based on target vs node.val?
   → YES: O(h) solution exists — implement as while loop traversal
   → NO: full O(n) traversal needed

2. WHAT TRAVERSAL ORDER GIVES THE ANSWER?
   □ Ascending order needed → inorder (L → Root → R)
   □ Descending order needed → reverse inorder (R → Root → L)
   □ Level-based needed → BFS with queue
   □ Subtree info before parent → postorder

3. FOR VALIDATION PROBLEMS:
   □ Never check only parent-child pairs
   □ Pass [min, max] range downward: left gets (min, node.val), right gets (node.val, max)
   □ Use long/float boundaries to handle integer edge cases

4. FOR CONSTRUCTION PROBLEMS:
   □ Given sorted array → mid as root, recurse halves
   □ Given preorder → first element is root, partition by value
   □ Given inorder → combine with preorder/postorder to reconstruct

5. FOR RANGE PROBLEMS:
   □ Prune left subtree when node.val ≤ lo (all left values are too small)
   □ Prune right subtree when node.val ≥ hi (all right values are too large)
   □ Include node when lo ≤ node.val ≤ hi

6. EDGE CASES FOR BST:
   □ Empty tree → return null/0/false as appropriate
   □ Single node → check if it's the answer itself
   □ k > total nodes → return -1 or handle gracefully
   □ Integer overflow in validation → use long, not int
   □ Equal values → clarify: strict BST (no duplicates) or allow?

Pattern Recognition Quick Reference

Difficulty Progression Reference

Common Interview Topics by Company Focus

Product-based companies (FAANG-tier):

• ›Validate BST — nearly universal
• ›Kth Smallest Element — core BST traversal
• ›LCA of BST — BST-specific vs general LCA contrast
• ›Serialize and Deserialize BST — design + traversal combination
• ›All Nodes at Distance K — multi-technique problem
• ›Recover BST — inorder violation detection
• ›Convert Sorted Array to BST — construction

Service-based and on-campus:

• ›Search, Insert, Delete in BST — fundamentals
• ›Inorder Successor/Predecessor — traversal mechanics
• ›Floor and Ceiling — BST property application
• ›Range Sum of BST — pruning technique

Startup and mid-size tech:

• ›BST Iterator — design interview
• ›Balance a BST — construction + inorder
• ›Two Sum in BST — set + traversal combo
• ›Largest BST Subtree — postorder aggregation

Progress Tracking

After solving each BST problem, record:

1. ›Pattern — which of the 6 patterns does this belong to?
2. ›BST property used — did you eliminate subtrees (O(h)) or traverse all (O(n))?
3. ›Traversal direction — inorder, reverse inorder, preorder, or BST property traversal?
4. ›Edge cases handled — empty tree, single node, k > n, integer overflow?
5. ›Time/space achieved — O(h), O(log n), O(n), O(k)?
6. ›Time to solve — target 15-20 minutes for easy, 25-30 minutes for medium

The decisive signal that BST pattern recognition is working: when you read "kth smallest element in BST" and immediately think "inorder traversal, stop at k — O(h + k) with iterative stack, O(k) amortised per call" — before reading the constraints or examples.