Binary Search Tree

Binary Search Tree is a Data Structure topic with 200+ LeetCode problems.

Related files: binary-tree.md · depth-first-search.md · binary-search.md · segment-tree.md

---

Core Concepts

BST — a binary tree where for every node v, all values in v's left subtree are strictly less than v.val, and all values in v's right subtree are strictly greater. This ordering makes in-order traversal yield a sorted sequence.

In-order predecessor — the largest value smaller than v; found as the rightmost node in v's left subtree, or the first ancestor for which v is in its right subtree.

In-order successor — the smallest value larger than v; found as the leftmost node in v's right subtree, or the first ancestor for which v is in its left subtree.

Floor — largest key ≤ target; equals the predecessor when target is not present, or the node itself when target is present.

Ceiling — smallest key ≥ target; equals the successor when target is not present, or the node itself when target is present.

Height — max edges from root to leaf; O(log n) when balanced, O(n) when degenerate.

Rank — number of keys strictly less than a given key; requires augmentation (see Augmented BST in Advanced Techniques).

Order statistic — the k-th smallest element; answered in O(log n) with size-augmented nodes, O(n) otherwise.

Validity — a BST's ordering constraint is non-local: it is not enough that each node is greater than its left child and less than its right child. The constraint must hold relative to all ancestors. A common mistake is checking only the immediate parent.

---

Structural Invariants

The BST invariant is non-local: a node might satisfy left.val < node.val < right.val and still be an invalid BST if an ancestor bound is violated. Validation must thread min/max bounds down the tree.

---

Internal Representation

Pointer-based (standard for LeetCode) Each node is a TreeNode object with val, left, right. Navigation is by following child pointers. Supports arbitrary shapes. All LeetCode BST problems use this representation. Space O(n).

Size-augmented nodes Add a size field counting nodes in the subtree rooted at each node. Enables O(log n) rank and order-statistic queries. Must be updated on every insert and delete. Used in problems asking for the k-th smallest or count of elements in a range.

Parent-pointer augmentation Add a parent field to each node. Needed for O(log n) successor/predecessor without a stack. Rarely provided in LeetCode but may need to be simulated with a stack during traversal.

Sorted array / balanced BST duality A sorted array and a balanced BST contain equivalent information. Conversion in both directions is a common problem class: sorted array → BST (binary-divide-and-recurse on the array midpoint), BST → sorted array (in-order traversal).

---

Types / Variants

For LeetCode: the BST structure is always provided as a pointer-based unbalanced BST. Balancing variants appear only in design problems (e.g., "implement a balanced BST") or implicitly via sortedcontainers.

---

Traversals & Access Patterns

In-order (Left → Root → Right)

Yields keys in sorted ascending order. The most-used traversal for BST problems. Any property that depends on sorted order (k-th smallest, range sum, check validity) is computed most naturally here.

Iterative in-order is required when the problem disallows O(n) extra space or when simulating an iterator (e.g., BST iterator problem):

stack, cur = [], root
while stack or cur:
    while cur: stack.append(cur); cur = cur.left
    cur = stack.pop(); visit(cur); cur = cur.right

Reverse in-order (Right → Root → Left)

Yields keys in descending order. Used for problems that need the k-th largest or want to accumulate a running suffix sum (e.g., convert BST to greater sum tree).

Pre-order (Root → Left → Right)

Encodes the BST's structure (not just its sorted content). The root always appears first, so pre-order uniquely reconstructs the BST without needing in-order. Used in serialization, cloning, and problems like "construct BST from preorder traversal."

Binary search descent (path traversal)

Not a full traversal — follows the BST property to descend to a target in O(h) time. The core of search, insert, floor, ceil, and successor/predecessor. Unlike general DFS, it visits at most one node per level.

Morris in-order (O(1) space)

Threads the rightmost node of the left subtree back to the current node; unthreads after visiting. Enables in-order traversal without a stack. Used when space is constrained. Modifies the tree transiently but restores it on completion.

See binary-tree.md for full traversal coverage including level-order, post-order, and Euler tour.

---

Topic-Specific Operations

Search

Descend left if target < node.val, right if target > node.val. Return node when target == node.val or null when falling off the tree. Time O(h).

Insert

Follow the same descent as search. Insert a new leaf at the first null position reached. The parent of the new leaf is the last non-null node visited. Time O(h).

Delete

Three cases based on the node to delete (call it d):

1. Leaf — remove directly; set parent's child pointer to null.
2. One child — bypass d by linking d's parent directly to d's single child.
3. Two children — replace d's value with its in-order successor (leftmost node in d's right subtree), then delete that successor (which has at most one right child — case 1 or 2).

if not root: return None
if val < root.val: root.left = delete(root.left, val)
elif val > root.val: root.right = delete(root.right, val)
else:
    if not root.left: return root.right
    if not root.right: return root.left
    # two children: replace with in-order successor

(The successor-finding and pointer update complete the 5-line body.) Time O(h).

Floor

Largest key ≤ target. Descend: if target == node.val, return it. If target < node.val, floor must be in left subtree. If target > node.val, floor is node.val or something larger in the right subtree — recurse right and return node if right yields nothing. Time O(h).

Ceiling

Smallest key ≥ target. Mirror of floor: descend right when target > node.val; return node if right subtree yields nothing. Time O(h).

Predecessor

Largest key strictly less than node.val. If node has a left subtree, it is the rightmost node there. Otherwise, traverse ancestors upward until a right-turn is found. Time O(h).

Successor

Smallest key strictly greater than node.val. If node has a right subtree, it is the leftmost node there. Otherwise, traverse ancestors upward until a left-turn is found. Time O(h).

K-th Smallest

Without augmentation: in-order traversal counting to k. Time O(n). With size augmentation: compare k against root.left.size; descend left if k ≤ left_size, return root if k == left_size+1, else descend right with adjusted k. Time O(h).

---

Key Algorithms

Validate BST

Verify that every node satisfies its ancestor-imposed bounds, not just its parent.

Key insight: Thread (lo, hi) bounds down the tree. At each node, check lo < node.val < hi. Pass (lo, node.val) left and (node.val, hi) right. Initial call uses (-inf, +inf).

def valid(node, lo, hi):
    if not node: return True
    if not (lo < node.val < hi): return False
    return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)

Time O(n), space O(h).

In-order to Validate / Extract Sorted Sequence

Iterative in-order traversal tracking the previous value. If any node's value ≤ prev, the BST property is broken. O(n) time, O(h) space (stack). Alternative to bounds-threading when only validity (not which node is invalid) is needed.

Lowest Common Ancestor (LCA) in BST

Both p and q are in the tree; use BST ordering to avoid full tree traversal.

Key insight: The LCA is the first node where p and q diverge (one goes left, one goes right). Descend: if both p.val and q.val < node.val, LCA is in left subtree; if both > node.val, in right subtree; otherwise, node is the LCA.

while root:
    if p.val < root.val and q.val < root.val: root = root.left
    elif p.val > root.val and q.val > root.val: root = root.right
    else: return root

Time O(h), space O(1) — strictly better than the general binary tree LCA.

Convert Sorted Array to Balanced BST

Recursively pick the midpoint as the root, recurse on left and right halves.

Key insight: Midpoint choice ensures height ≤ ⌈log₂ n⌉. Both mid = (lo+hi)//2 (left-leaning) and mid = (lo+hi+1)//2 (right-leaning) produce valid balanced BSTs; the problem may accept either or specify uniqueness.

Time O(n), space O(log n) stack.

Convert BST to Greater Sum Tree (Reverse Cumulative Sum)

Replace each node's value with the sum of all values ≥ it. Reverse in-order (right → root → left) with a running cumulative sum. Single pass. Time O(n).

Recover BST (Two Nodes Swapped)

Two nodes have been swapped; restore the BST. During in-order traversal, a violation occurs when the current node's value is less than the previous node. First violation: first = prev, second = curr. Second violation (if it occurs): second = curr. Swap first.val and second.val.

Key insight: There are exactly two violations if the swapped nodes are non-adjacent in sorted order, one violation if adjacent. Always update second; only set first on the first violation. Morris traversal reduces space to O(1).

Time O(n), space O(h) recursive or O(1) with Morris.

Delete Node in BST

See Topic-Specific Operations. The two-children case is the only non-trivial one: find the in-order successor (leftmost of right subtree), copy its value up, then recursively delete it from the right subtree.

Insert into BST

Recursive descent to the null insertion point; return the new node upward. Alternatively, iterative with parent tracking. Time O(h).

Range Sum / Count in BST

Sum (or count) all nodes with values in [lo, hi]. Descent: skip left subtree if node.val ≤ lo, skip right subtree if node.val ≥ hi, otherwise add node.val and recurse both. Time O(h + k) where k is the number of nodes in range.

Kth Smallest in BST

Iterative in-order with a counter. Stop and return at count = k. Time O(h + k), space O(h). With size augmentation: O(h) without counting all nodes.

BST Iterator

Simulate in-order traversal on-demand. Maintain a stack; next() pops and moves to right subtree, hasNext() checks if stack is non-empty. Each call amortizes to O(1) — total O(n) over all calls.

---

Advanced Techniques

Augmented BST (Size / Count Field)

What it solves: Problems requiring rank queries ("how many elements < x"), order statistics ("k-th smallest"), and count-in-range in O(log n) rather than O(n).

Core mechanism: Each node stores size = 1 + left.size + right.size. On insert/delete, update all ancestor sizes. Rank(x) = left.size + 1 if found; otherwise accumulate left sizes along the search path.

When to use over simpler alternatives: Use when the problem requires multiple rank/order-statistic queries (online), making O(n) per query unacceptable. For a single k-th smallest with no updates, plain in-order traversal suffices.

Complexity: O(h) per augmented query; O(n) space overhead.

Morris Traversal on BST

What it solves: In-order traversal with O(1) extra space. Required when the problem forbids recursion and limits extra space, or asks for an explicit O(1)-space solution.

Core mechanism: Thread the rightmost node of each left subtree's right spine back to the current node. Detect the thread on the second visit to unthread and visit the node.

When to use over simpler alternatives: Only when O(log n) stack space is explicitly forbidden. The iterative stack approach is simpler and equally correct in all other cases.

Complexity: O(n) time, O(1) space.

BST as a Sorted Set / Multiset via sortedcontainers

What it solves: Online problems needing dynamic insert, delete, rank, floor, ceil, predecessor, and successor — exactly what a balanced BST provides.

Core mechanism: Python's sortedcontainers.SortedList (or SortedDict) provides O(log n) add/remove and O(log n) bisect (equivalent to floor/ceil). Use sl.bisect_left(x) for ceiling index, sl[idx] for order statistics.

When to use over simpler alternatives: Use when the problem requires multiple operation types on a dynamic dataset. If only sorted iteration is needed after all inserts, a list + sort is simpler. If only frequency counts are needed, a Counter suffices.

Complexity: O(log n) per operation, O(n) space.

Offline Coordinate Compression + BIT/Segment Tree

What it solves: "Count inversions," "count elements in a range seen so far," and similar problems that look like BST order-statistic queries but appear in bulk.

Core mechanism: Compress all values to ranks 1…n, then use a Binary Indexed Tree (BIT) for prefix counts. Equivalent to an augmented BST in expressiveness but more cache-friendly.

When to use over augmented BST: When all queries are known upfront (offline), when the value range is large but the number of distinct values is bounded, or when BIT is simpler to implement than augmented BST from scratch.

Complexity: O(n log n) preprocessing, O(log n) per query.

Treap / Randomized BST

What it solves: Design problems requiring a hand-rolled balanced BST with O(log n) expected height — no rotations, simpler than AVL.

Core mechanism: Each node has a BST key and a random priority. Maintain BST order by key and heap order by priority. Split and merge operations handle insert/delete.

When to use over AVL/Red-Black: When implementing from scratch during an interview and rotation logic is error-prone. Expected O(log n) is sufficient for most problems; deterministic balance is rarely required.

Complexity: O(log n) expected per operation, O(n) space.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Non-local BST invariant violation. Checking only left.val < node.val < right.val misses cases where a node violates an ancestor's bound. Fix: use bounds threading (lo, hi) through the recursion. A common invalid BST that passes the naive check: 5 → left=4 → right=6; 6 > 5 so it fails the root's right-bound constraint.

• Single-node tree. Many traversal loops assume at least two nodes. A single-node BST is valid, its LCA with itself is itself, and its k-th smallest (for k=1) is just the root. Ensure base cases return early cleanly.

• Duplicate values. Standard BST definition forbids duplicates. If the problem allows them (e.g., "not necessarily distinct"), the strict inequality invariant breaks — search and delete become ambiguous. Clarify before coding; adjust to ≤ / ≥ if needed and handle delete by choosing a consistent side.

• Degenerate (skewed) BST. Inserting sorted input into a BST gives O(n) height. Algorithms that are O(h) become O(n), which may TLE. If the problem guarantees a balanced BST, state it; otherwise assume O(n) worst case.

• Recover BST: single vs. double violation. If the two swapped nodes are adjacent in sorted order, only one violation appears in the in-order traversal. Always record second = curr on every violation but only set first = prev once. Failing to handle the single-violation case leaves one of the two pointers unset.

• Delete: forgetting to return the updated subtree root. Recursive delete must return node at the end so the parent can re-link. Omitting the return leaves dangling pointers; the tree silently loses nodes.

• LCA in BST vs. general LCA. The BST LCA uses O(h) descent; applying the general O(n) post-order LCA to a BST is correct but wastes the ordering property. In interviews, explicitly note which algorithm you are using.

• In-order prev comparison using value vs. node. Storing only the previous value loses the ability to return the node for recover-BST. Store the previous node reference (self.prev = None; update to the node after visiting).

• Off-by-one in k-th smallest countdown. Decrement k when visiting a node, not before or after. If k reaches 0 before the traversal ends, stop early. Continuing the full traversal is wasteful but not incorrect; not stopping early may TLE on large inputs.

• Morris traversal: double modification. Morris traversal temporarily modifies the tree. Do not call any function that reads or modifies the tree concurrently. Restore is automatic only if the traversal completes without early exit — if you break out early, the tree may be left threaded.

---

Implementation Notes

• LeetCode BST nodes use TreeNode with val, left, right. There is no parent or size field; augmentation must be added manually if needed.
• Python recursion limit defaults to 1000. A degenerate BST of height 1000 will hit RecursionError. Use sys.setrecursionlimit(10000) or convert to iterative for production-quality solutions.
• float('-inf') and float('inf') are valid sentinels for BST bounds threading. They compare correctly with integers in Python.
• sortedcontainers.SortedList is available in LeetCode Python environments and provides O(log n) add, remove, bisect_left, bisect_right, and index access — equivalent to an augmented BST without implementation overhead.
• When using sortedcontainers.SortedList.remove(x), it removes only one occurrence. For a multiset, use discard carefully or track counts separately.
• The bisect module's bisect_left(sl, x) on a SortedList gives the index of the floor+1; sl[idx-1] is the floor value. Ensure idx > 0 before accessing.
• Recursive BST functions typically need a return value (the possibly updated subtree root). A common mistake is writing the recursion without returning the result of each recursive call.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Validation & Construction

• Validate Binary Search Tree (LeetCode 98) — bounds threading
• Convert Sorted Array to Binary Search Tree (LeetCode 108) — midpoint recursion
• Construct BST from Preorder Traversal (LeetCode 1008) — bounds threading during construction

Search & Modification

• Search in a Binary Search Tree (LeetCode 700) — basic descent
• Insert into a Binary Search Tree (LeetCode 701) — leaf insertion
• Delete Node in a BST (LeetCode 450) — three-case deletion
• Lowest Common Ancestor of a BST (LeetCode 235) — divergence-point descent

Order Statistics & Range

• Kth Smallest Element in a BST (LeetCode 230) — in-order countdown
• Range Sum of BST (LeetCode 938) — pruned descent
• Count of Smaller Numbers After Self (LeetCode 315) — augmented BST or BIT

Conversion & Restructure

• Convert BST to Greater Tree (LeetCode 538) — reverse in-order accumulation
• Balance a Binary Search Tree (LeetCode 1382) — in-order to array, midpoint construct
• Recover Binary Search Tree (LeetCode 99) — in-order prev tracking, two violations

Design & Advanced

• Binary Search Tree Iterator (LeetCode 173) — stack-based iterative in-order
• Serialize and Deserialize BST (LeetCode 449) — preorder encoding with bounds
• Closest Binary Search Tree Value II (LeetCode 272) — two-pointer on in-order predecessor/successor stacks

Additional LeetCode Coverage

• Inorder Successor in BST (LC 285)
• Minimum Absolute Difference in BST (LC 530)
• Two Sum IV - Input is a BST (LC 653)
• Construct Binary Search Tree from Preorder Traversal (LC 1008)
• Maximum Sum BST in Binary Tree (LC 1373)
• Lowest Common Ancestor of a Binary Search Tree (LC 235)

Clarification Questions to Ask

• Are node values guaranteed to be unique, or can duplicates exist?
• Is the BST guaranteed to be balanced, or can it be degenerate (up to O(n) height)?
• For LCA: are both nodes guaranteed to be present in the tree?
• For k-th smallest: is k guaranteed to be ≤ the number of nodes?
• For "path": does it mean root-to-leaf, or any node-to-node path?
• Are negative values possible? (Affects sentinel choices for floor/ceil and validity bounds.)
• For design problems: what operations need to be O(log n), and which can be O(n)?

Common Interview Mistakes

• Validating BST by checking only left.val < node.val < right.val without threading ancestor bounds — fails on inputs like [5, 1, 4, null, null, 3, 6] where 3 < 5 is invisible to its local parent.
• Using the general O(n) LCA algorithm on a BST instead of the O(h) divergence-point descent — correct but wastes the BST property; interviewers expect you to notice.
• Forgetting to return node at the end of recursive delete/insert, leaving the caller unable to re-link the modified subtree.
• Handling only one violation in recover-BST, missing the adjacent-nodes case where the swap produces a single violation in the in-order sequence.
• Not handling the case where the BST is a single node in operations like insert (no-op), delete (return null), or LCA (trivial).
• Confusing bisect_left (first index ≥ x) with bisect_right (first index > x) when implementing floor/ceil manually.
• Assuming O(log n) time for operations on an unbalanced BST provided by the problem — always state O(h) and note that h can be O(n).

Typical Follow-Up Escalations

• "Now solve it without recursion." → Iterative in-order with an explicit stack; for delete, iterative descent tracking parent and direction.
• "Now solve it in O(1) extra space." → Morris traversal for traversal-based solutions; O(h) iterative loop for search/insert.
• "Now handle frequent insertions and k-th smallest queries." → Augment each node with a size field; update on each insert/delete for O(h) order statistics.
• "Now do it for a stream of values." → Use sortedcontainers.SortedList for O(log n) insert and O(log n) rank; or maintain an augmented BST.
• "What if the BST can become unbalanced?" → Describe AVL or Red-Black trees; explain rotation mechanics at a high level; note that Python's sortedcontainers handles this in practice.
• "Can you serialize a BST more compactly than a general binary tree?" → Yes: preorder traversal suffices (no nulls needed) because BST bounds reconstruct the structure; this is O(n) vs. O(2n) for a general tree.