- Understand BST invariant: left < root < right for all nodes
- Implement search, insert, delete in O(h) where h is height
- Avoid degenerate trees (linked list) by understanding balance importance
Binary Search Trees (BST)
You need a dictionary. Fast lookups. Fast insertions. Fast deletions.
Arrays give O(log n) search if sorted (binary search), but O(n) insertion/deletion (shifting elements). Hash tables give O(1) average, but no order.
Binary Search Trees give O(log n) for all three operations (on average) AND maintain order.
What's a BST?
A binary tree with an ordering property:
- For every node: all values in left subtree < node's value < all values in right subtree
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Valid BST. For node 8: left subtree {1, 3, 4, 6, 7} all < 8, right subtree {10, 13, 14} all > 8.
Search
Looking for 6:
Start at root (8). 6 < 8, go left.
At 3. 6 > 3, go right.
At 6. Found!
def search(root, target):
if root is None:
return False
if root.value == target:
return True
elif target < root.value:
return search(root.left, target)
else:
return search(root.right, target)
O(h) where h is height. Balanced tree: h = log n. Worst case (degenerate): h = n.
Iterative:
def search_iterative(root, target):
current = root
while current:
if current.value == target:
return True
elif target < current.value:
current = current.left
else:
current = current.right
return False
Same complexity, no recursion overhead.
Insert
Insert 5 into the tree:
Start at root (8). 5 < 8, go left.
At 3. 5 > 3, go right.
At 6. 5 < 6, go left.
At 4. 5 > 4, go right.
Right child is null. Insert 5 there.
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
# If value == root.value, ignore (no duplicates)
return root
O(h). Finds insertion point, creates new node.
Delete
Three cases:
1. Leaf node (no children): Just remove it.
Delete 1:
8 8
/ \ / \
3 10 => 3 10
/ \ \ \ \
1 6 14 6 14
2. One child: Replace node with its child.
Delete 10:
8 8
/ \ / \
3 10 => 3 14
/ \ \ / \ /
1 6 14 1 6 13
\ / \
7 13 7
3. Two children: Replace with inorder successor (smallest in right subtree) or predecessor (largest in left subtree).
Delete 3:
8 8
/ \ / \
3 10 => 4 10
/ \ \ / \ \
1 6 14 1 6 14
/ \ / \ /
4 7 13 7 13
Inorder successor of 3 is 4 (smallest in right subtree). Copy 4's value to 3's position, delete 4 (which is now a leaf or has one child).
def delete(root, value):
if root is None:
return None
if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
# Found node to delete
# Case 1: Leaf or one child
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Case 2: Two children
# Find inorder successor (min in right subtree)
min_node = find_min(root.right)
root.value = min_node.value
root.right = delete(root.right, min_node.value)
return root
def find_min(node):
while node.left:
node = node.left
return node
O(h). Find node, handle deletion cases.
Inorder Traversal = Sorted Order
Inorder of BST gives sorted values.
def inorder(root):
if root is None:
return
inorder(root.left)
print(root.value)
inorder(root.right)
For the example tree: 1, 3, 4, 6, 7, 8, 10, 13, 14
Sorted! That's the BST property at work.
Validate BST
Check if a tree is a valid BST.
Wrong approach: Just check left < root < right for each node. Doesn't catch violations in subtrees.
5
/ \
3 7
\
6
Looks OK locally. But 6 is in left subtree of 5, violating 6 < 5.
Correct approach: Track valid range for each node.
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if root is None:
return True
if root.value <= min_val or root.value >= max_val:
return False
return (is_valid_bst(root.left, min_val, root.value) and
is_valid_bst(root.right, root.value, max_val))
For left child, max becomes root's value. For right child, min becomes root's value.
Find K-th Smallest
Use inorder traversal (gives sorted order).
def kth_smallest(root, k):
result = [None]
counter = [0]
def inorder(node):
if node is None or result[0] is not None:
return
inorder(node.left)
counter[0] += 1
if counter[0] == k:
result[0] = node.value
return
inorder(node.right)
inorder(root)
return result[0]
Visit nodes in sorted order. When counter reaches k, that's the k-th smallest.
O(k + h) in best case (stop early), O(n) worst case.
Lowest Common Ancestor (LCA)
Find lowest common ancestor of two nodes in BST.
Use BST property: if both values < root, LCA in left. If both > root, LCA in right. Otherwise, root is LCA.
def lca(root, p, q):
if root is None:
return None
if p.value < root.value and q.value < root.value:
return lca(root.left, p, q)
elif p.value > root.value and q.value > root.value:
return lca(root.right, p, q)
else:
return root
O(h). First node where paths diverge.
Build BST from Sorted Array
Sorted array: [1, 3, 4, 6, 7, 8, 10, 13, 14]
To get balanced BST, pick middle as root. Recursively build left and right subtrees.
def sorted_array_to_bst(arr):
if not arr:
return None
mid = len(arr) // 2
root = TreeNode(arr[mid])
root.left = sorted_array_to_bst(arr[:mid])
root.right = sorted_array_to_bst(arr[mid+1:])
return root
O(n). Visit each element once. Produces balanced BST (height = log n).
Degenerate BST
Insert in sorted order: 1, 2, 3, 4, 5
1
\
2
\
3
\
4
\
5
Linked list! Height = n. All operations O(n). Terrible.
Solution: self-balancing BSTs (AVL, Red-Black). Guarantee height = O(log n).
When to Use BST
Ordered data with frequent modifications: BST maintains order while allowing O(log n) insert/delete (unlike sorted arrays with O(n) insert/delete).
Range queries: Find all values in [a, b]. Inorder traversal, stop when out of range.
Nearest neighbor: Find closest value to target. Navigate tree comparing distances.
When NOT to Use BST
Unordered lookups only: Hash table is O(1) average, better than BST's O(log n).
Data already sorted, rarely modified: Array with binary search is simpler.
Worst-case guarantees needed: Use self-balancing BST (AVL, Red-Black) instead of plain BST.
The Power
BST combines binary search's efficiency with tree's flexibility:
- O(log n) search (if balanced)
- O(log n) insert (if balanced)
- O(log n) delete (if balanced)
- Maintains order (inorder traversal)
Understanding BST means understanding:
- The ordering invariant (left < root < right)
- How to maintain it during operations
- The balance problem (degenerate trees)
Master BST, and you'll appreciate balanced variants (AVL, Red-Black) and more complex structures (B-trees).