Binary Search Trees: Complete Interview Playbook
Master BST fundamentals, insertion, traversal, and interview-ready code (recursive & iterative).
1. What is a BST?
A Binary Search Tree is a binary tree where every node obeys a single invariant:
For any node N, all values in its left subtree are strictly less than N, and all values in its right subtree are strictly greater than N. This holds recursively at every node.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
This ordering lets you binary-search the tree just like a sorted array. Each comparison eliminates half the remaining candidates — giving O(log n) expected performance for all core operations.
The single most useful property: Inorder traversal (left → root → right) of a BST always produces values in sorted ascending order. You will exploit this in Kth Smallest, Inorder Successor, and validation problems.
Node structure
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
2. Insert
Intuition
Inserting a value is a guided descent from the root. At each node, the BST property tells you exactly which direction to go. When you fall off the tree (hit None), you've found the right spot
Recursive implementation
def insert(root, val):
if not root:
return TreeNode(val) # found the empty slot
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val:
root.right = insert(root.right, val)
# val == root.val → duplicate; ignore (standard BST convention)
return root
The key insight: every recursive call returns the (possibly new) root of that subtree. The parent wires up root.left = ... or root.right = ... with whatever comes back. This is a clean way to handle node creation without special-casing the parent pointer.
Iterative implementation
def insert_iter(root, val):
node = TreeNode(val)
if not root:
return node
cur = root
while True:
if val < cur.val:
if cur.left is None:
cur.left = node
break
cur = cur.left
else:
if cur.right is None:
cur.right = node
break
cur = cur.right
return root
The iterative version uses O(1) extra space instead of O(h) call-stack space. In skewed trees with n = 10⁵ nodes, recursion can overflow the stack — prefer iterative in interviews unless you explicitly discuss it.
Step-by-step trace — inserting 5 into the example tree
Start at root = 8 → 5 < 8 → go left
At node 3 → 5 > 3 → go right
At node 6 → 5 < 6 → go left
At node 4 → 5 > 4 → go right
At node None → place 5 here ✓
Complexity
| Case | Time | Space (recursive) |
|---|---|---|
| Balanced tree | O(log n) | O(log n) |
| Skewed tree (worst) | O(n) | O(n) |
Solve problem - Insert Into a Binary Search Tree
3. Search
Intuition
Identical motion to insert — follow the BST property downward. You stop when you either find the value or fall off the tree.
Recursive
def search(root, target):
if not root or root.val == target:
return root # None → not found; node → found
if target < root.val:
return search(root.left, target)
return search(root.right, target)
Iterative (preferred in interviews)
def search_iter(root, target):
while root and root.val != target:
root = root.left if target < root.val else root.right
return root
This is naturally tail-recursive, so the iterative form is direct. It avoids any stack overhead and is what you should default to.
Complexity
Same as insert: O(log n) balanced, O(n) worst case on a skewed tree.
Solve problem - Search in a Binary Tree
4. Delete
Delete is the hardest BST operation. Three structural cases arise based on how many children the target node has.
Case 1 — Leaf node (no children)
Simply return None to the parent. The node vanishes.
Delete 7 from the example tree:
6 6
/ \ → /
4 7 4
Case 2 — One child
Bypass the node entirely. Return its only child up to the parent.
Delete 10 (has only right child 14):
8 8
/ \ → / \
3 10 3 14
\ /
14 13
Case 3 — Two children (the tricky one)
You cannot simply remove the node because it holds structure together. The standard approach:
Find the inorder successor: the smallest value in the right subtree (go right once, then leftmost).
Copy that successor's value into the current node.
Delete the successor from the right subtree (it will have at most one child — a right child — since it's the leftmost node).
Why the inorder successor? Because it is the smallest value greater than the current node. Placing it here preserves the BST invariant: it's still greater than everything in the left subtree, and smaller than everything else in the right subtree.
Full implementation
def delete(root, key):
if not root:
return None
if key < root.val:
root.left = delete(root.left, key)
elif key > root.val:
root.right = delete(root.right, key)
else:
# Found the node to delete
if not root.left: # Case 1 or Case 2 (no left child)
return root.right
if not root.right: # Case 2 (no right child)
return root.left
# Case 3: two children
# Find inorder successor (min of right subtree)
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val # copy value up
root.right = delete(root.right, successor.val) # delete successor
return root
def find_min(node):
while node.left:
node = node.left
return node
Step-by-step trace — deleting 3 from the example tree
Target: 3 (two children: 1 and 6)
Inorder successor of 3 = min of right subtree of 3
→ go right to 6, then leftmost → 4
Copy 4 into node (was 3):
8
/ \
4 10 ← node now holds 4
/ \ \
1 6 14
/ \ /
4 7 13 ← this 4 still needs to be deleted
Delete 4 from right subtree of node-now-4:
4 has no left child → return its right child (None)
Final:
8
/ \
4 10
/ \ \
1 6 14
\ /
7 13
Complexity
| Case | Time |
|---|---|
| Balanced | O(log n) |
| Skewed (worst) | O(n) |
Solve problem - Delete Node in a BDelete Node in a BST
5. O(log n) vs O(n) — Why Worst Case is Linear
This is one of the most common follow-up questions in interviews. You must be able to explain it clearly.
Why O(log n)?
In a perfectly balanced BST with n nodes, the height h = log₂(n). Every operation (insert, search, delete) does at most one comparison per level, so it visits at most h nodes → O(log n) (height of tree)
Why O(n)?
The BST property says nothing about balance. If you insert already-sorted data, every new node goes to the right of the previous one:
Insert: 1, 2, 3, 4, 5
1
\
2
\
3
\
4
\
5
This is a valid BST — the invariant holds — but it's structurally a linked list. Height = n. Searching for 5 visits all 5 nodes → O(n).
The core tradeoff
| Tree shape | Height | Operation time |
|---|---|---|
| Perfect balance | log n | O(log n) |
| Random inserts (average) | ~1.39 log n | O(log n) |
| Sorted inserts (worst) | n | O(n) |
| Reverse-sorted inserts (worst) | n | O(n) |
How do self-balancing BSTs fix this?
AVL trees and Red-Black trees add rotation rules that maintain height ≤ O(log n) after every insert and delete. Python's SortedList (from sortedcontainers) and Java's TreeMap are backed by these structures. For interviews, you don't implement them from scratch — but knowing they exist and why is expected.
What to say in an interview
BST gives O(log n) average case assuming the tree is reasonably balanced. In the worst case — when input is sorted or reverse-sorted — the tree degenerates into a linked list and all operations become O(n). This is why production systems use self-balancing variants like AVL or Red-Black trees.
6. Validate BST
LeetCode 98 — Validate Binary Search Tree (Medium)
The naive mistake
A common wrong approach: check that node.left.val < node.val < node.right.val at every node. This fails on cases like:
5
/ \
1 4
/ \
3 6
At node 4: 3 < 4 < 6 ✓ locally. But 3 and 4 are in the right subtree of 5, so they must all be > 5. This tree is invalid and the local check misses it.
Correct approach: pass valid range down
Every node must satisfy min_val < node.val < max_val. As you recurse, tighten the bounds:
Going left: the current node's value becomes the new upper bound.
Going right: the current node's value becomes the new lower bound.
def isValidBST(root):
def validate(node, min_val, max_val):
if not node:
return True
if not (min_val < node.val < max_val):
return False
return (validate(node.left, min_val, node.val) and
validate(node.right, node.val, max_val))
return validate(root, float('-inf'), float('inf'))
Trace through the invalid example above
validate(5, -inf, +inf) → -inf < 5 < +inf ✓
validate(1, -inf, 5) → -inf < 1 < 5 ✓
validate(4, 5, +inf) → 5 < 4 < +inf ✗ → return False
Returns False correctly.
Alternative: inorder traversal must be strictly increasing
def isValidBST_inorder(root):
prev = [float('-inf')] # use list for mutability in closure
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]:
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
This works because inorder traversal of a valid BST must produce a strictly increasing sequence. If any value is ≤ the previous, the BST property is violated.
Both approaches are O(n) time, O(h) space. The bounds-passing approach is slightly more intuitive to explain; the inorder approach leverages the sorted-inorder property directly.
7. Kth Smallest Element in a BST
LeetCode 230 — Kth Smallest Element in a BST (Medium)
Key insight
Inorder traversal visits BST nodes in ascending order. The kth node visited is the kth smallest. No sorting needed — the BST structure gives it to you.
Recursive approach
def kthSmallest(root, k):
result = [0]
count = [0]
def inorder(node):
if not node or count[0] == k:
return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]
Iterative approach (preferred — avoids recursion limit)
def kthSmallest_iter(root, k):
stack = []
cur = root
while cur or stack:
while cur: # go as far left as possible
stack.append(cur)
cur = cur.left
cur = stack.pop() # visit
k -= 1
if k == 0:
return cur.val
cur = cur.right # move to right subtree
Trace on the example tree, k=3
Push: 8 → 3 → 1
Pop 1: k=3→2, cur=None
Pop 3: k=2→1, cur=6
Push: 6 → 4
Pop 4: k=1→0 → return 4 ✓
Sorted order: 1, 3, 4, 6, 7, 8, 10, 13, 14
3rd smallest = 4
Complexity
O(h + k) time (h to reach the leftmost, then k pops), O(h) space for the stack.
Follow-up question: "What if inserts/deletes happen frequently and you need kth smallest after each operation?" The answer is to augment each node with a left_count field (size of left subtree). Then you can find kth in O(log n) without traversal.
8. Convert Sorted Array to BST
LeetCode 108 — Convert Sorted Array to Binary Search Tree (Easy)
Problem
Given a sorted array, construct a height-balanced BST. Height-balanced means the height difference between left and right subtrees of any node is at most 1.
Insight
The middle element of the array should become the root. Everything to its left forms the left subtree; everything to its right forms the right subtree. Apply this recursively on each half.
This is the same principle as binary search: always pick the midpoint.
def sortedArrayToBST(nums):
def build(lo, hi):
if lo > hi:
return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid])
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(nums) - 1)
Trace on [1, 2, 3, 4, 5, 6, 7]
build(0, 6) → mid=3 → root=4
build(0, 2) → mid=1 → node=2
build(0, 0) → mid=0 → node=1 (leaf)
build(2, 2) → mid=2 → node=3 (leaf)
build(4, 6) → mid=5 → node=6
build(4, 4) → mid=4 → node=5 (leaf)
build(6, 6) → mid=6 → node=7 (leaf)
Result:
4
/ \
2 6
/ \ / \
1 3 5 7
Perfectly balanced: every level is filled. Height = log₂(7) ≈ 3.
Complexity
O(n) time (each element visited once), O(log n) space (recursion depth = height of balanced tree).
Variant: LeetCode 109 — Convert Sorted List to BST. Same idea, but you can't index into a linked list. Use slow/fast pointers to find the midpoint, then recurse on each half. O(n log n) time unless you use inorder simulation.
9. Inorder Successor and Predecessor
These are two of the most asked BST problems in onsite interviews. Understand them cold.
Definitions
Inorder successor of node P: the node with the smallest value greater than P.val. In inorder traversal, it's the node that comes immediately after P.
Inorder predecessor of node P: the node with the largest value less than P.val. In inorder traversal, it's the node that comes immediately before P.
Case analysis for Inorder Successor
Case 1: P has a right subtree. The successor is the leftmost node in P's right subtree (the minimum of the right subtree).
Successor of 3 in the example tree:
3 has right subtree rooted at 6
Leftmost of that subtree = 4
→ successor is 4
Case 2: P has no right subtree. Walk up the tree using parent pointers. The successor is the first ancestor for which P is in the left subtree (the first ancestor with a greater value).
Successor of 7 in the example tree:
7 has no right child
Go up: parent is 6 → 7 is in 6's right subtree → skip
Go up: parent is 3 → 6 is in 3's right subtree → skip
Go up: parent is 8 → 3 is in 8's left subtree → 8 is the ancestor ✓
→ successor is 8
Implementation (with parent pointers)
def inorder_successor(root, p):
successor = None
cur = root
while cur:
if p.val < cur.val:
successor = cur # cur is a candidate
cur = cur.left # try to find something smaller
else:
cur = cur.right # p is >= cur, successor must be to the right
return successor
This elegant solution doesn't need parent pointers. It uses the BST property: at each node, if p.val < cur.val, cur is a valid successor candidate (record it and go left to find a smaller one). If p.val >= cur.val, the successor must be in the right subtree.
Case analysis for Inorder Predecessor
Mirror image of successor:
P has a left subtree: predecessor = rightmost node in left subtree (maximum of left subtree).
P has no left subtree: predecessor = first ancestor for which P is in the right subtree.
def inorder_predecessor(root, p):
predecessor = None
cur = root
while cur:
if p.val > cur.val:
predecessor = cur # cur is a candidate
cur = cur.right # try to find something larger
else:
cur = cur.left
return predecessor
Full trace — successor of 6
cur=8: 6 < 8 → successor=8, go left
cur=3: 6 > 3 → go right
cur=6: 6 == 6 → go right
cur=7: 6 < 7 → successor=7, go left
cur=None → stop
Return 7 ✓
Why this works without parent pointers
At every step, the BST property tells you: if p.val < cur.val, then cur is "to the right of" p in inorder, making it a valid successor. By always going left after recording a candidate, you find the smallest such ancestor — which is the true successor.
LeetCode 285 variant (with access to root only)
LeetCode 285 — Inorder Successor in BST — gives you the root and the target node p. The solution above handles it directly. LeetCode 510 — Inorder Successor in BST II — gives you direct access to the node with a parent pointer, enabling the classic two-case approach.
Problem - Inorder Successor in BST
10. LeetCode Problem List
Work through these in the order listed. The first five are the core operations; the last five are pattern extensions.
| # | Problem | Difficulty | Key concept |
|---|---|---|---|
| 700 | Search in a Binary Search Tree | Easy | Pure BST search |
| 701 | Insert into a Binary Search Tree | Medium | Recursive insert |
| 450 | Delete Node in a BST | Medium | 3-case delete |
| 98 | Validate Binary Search Tree | Medium | Range bounds, inorder |
| 230 | Kth Smallest Element in a BST | Medium | Inorder traversal |
| 108 | Convert Sorted Array to Binary Search Tree | Easy | Divide and conquer |
| 109 | Convert Sorted List to Binary Search Tree | Medium | Slow/fast pointer + 108 |
| 285 | Inorder Successor in BST | Medium | BST property descent |
| 510 | Inorder Successor in BST II | Medium | Parent pointer + 285 |
| 173 | Binary Search Tree Iterator | Medium | Iterative inorder |
Bonus (once you're comfortable)
| # | Problem | Difficulty | Key concept |
|---|---|---|---|
| 653 | Two Sum IV — Input is a BST | Easy | Inorder + two-pointer |
| 669 | Trim a Binary Search Tree | Medium | Recursive trim with bounds |
| 1038 | BST to Greater Sum Tree | Medium | Reverse inorder (right → root → left) |
| 99 | Recover Binary Search Tree | Hard | Two swapped nodes in inorder |
Quick Reference Card
INSERT → recurse left/right; place at first None; O(log n) avg, O(n) worst
SEARCH → recurse left/right; return node or None; O(log n) avg, O(n) worst
DELETE → 3 cases: leaf / one child / two children (use inorder successor)
VALIDATE → pass (min, max) bounds; tighten at each level; O(n)
KTH → iterative inorder; pop kth node; O(h + k)
BUILD → always pick midpoint as root; recurse on halves; O(n)
SUCCESSOR → has right child? → min(right subtree); else → first ancestor where you came from left
PREDECESSOR → has left child? → max(left subtree); else → first ancestor where you came from right
WORST CASE O(n): sorted/reverse-sorted input → skewed tree → height = n FIX: AVL tree, Red-Black tree, treap (all guarantee O(log n) worst case)
