10. Trees and BSTs
📋 Jump to TakeawaysTrees model hierarchical relationships. File systems, HTML documents, organization charts, decision processes — anything with a parent-child structure is a tree. In DSA, binary trees and binary search trees are the foundation for heaps, tries, segment trees, and most divide-and-conquer algorithms.
The Structure
A tree is a connected graph with no cycles. One node is the root. Every other node has exactly one parent and zero or more children.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 5
# / \
# 3 8
# / \ \
# 1 4 9Binary tree — each node has at most two children (left and right). Most interview problems use binary trees.
Terminology: root (top node), leaf (no children), depth (distance from root), height (longest path to a leaf).
Binary tree types:
| Type | Definition |
|---|---|
| Full | Every node has 0 or 2 children (never just 1) |
| Complete | All levels filled except possibly the last, which fills left to right (this is how heaps are structured) |
| Perfect | All internal nodes have 2 children AND all leaves at same depth |
| Balanced | Height is O(log n) — left and right subtrees differ in height by at most 1 |
| BST | For every node: left subtree < node < right subtree |
Traversals
Four ways to visit every node. Each produces a different order:
# Inorder: left → root → right (gives sorted order for BSTs)
def inorder(root: TreeNode | None) -> list[int]:
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
# Preorder: root → left → right (copy/serialize a tree)
def preorder(root: TreeNode | None) -> list[int]:
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# Postorder: left → right → root (delete a tree, evaluate expressions)
def postorder(root: TreeNode | None) -> list[int]:
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]Level-Order (BFS) with collections.deque
from collections import deque
def level_order(root: TreeNode | None) -> list[list[int]]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultUse collections.deque for BFS — popleft() is O(1). A regular list's pop(0) is O(n) because it shifts all elements.
DFS Patterns on Trees
Most tree problems are recursive DFS. The pattern: solve for left subtree, solve for right subtree, combine.
# Max depth — O(n)
def max_depth(root: TreeNode | None) -> int:
if not root:
return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
# Check if symmetric
def is_symmetric(root: TreeNode | None) -> bool:
def is_mirror(a, b):
if not a and not b:
return True
if not a or not b:
return False
return (a.val == b.val and
is_mirror(a.left, b.right) and
is_mirror(a.right, b.left))
return is_mirror(root.left, root.right) if root else TrueIterative DFS
Recursive DFS uses the call stack implicitly. Iterative DFS uses an explicit stack — useful when recursion depth could overflow (Python's default recursion limit is 1000) or when you need more control.
# Iterative inorder traversal — O(n) time, O(h) space
def inorder_iterative(root: TreeNode | None) -> list[int]:
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left # push all lefts
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return resultThe pattern: push all left children, pop and process, then go right. This gives sorted order for BSTs and is the basis for BST iterators.
Python recursion limit: For deep trees (10,000+ nodes), use sys.setrecursionlimit() or switch to iterative. Interview problems rarely hit this, but production code should be aware.
Lowest Common Ancestor (LCA)
The LCA of two nodes is the deepest node that is an ancestor of both. It's where the paths from root to each node diverge.
LeetCode 236 - Lowest Common Ancestor of a Binary Tree
def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root # p and q are on different sides
return left if left else rightLeetCode 235 - Lowest Common Ancestor of a BST
In a BST, LCA is simpler — use the BST property to decide which direction to go:
def lca_bst(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
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 # split pointBinary Search Trees
A BST adds one rule: for every node, all values in the left subtree are smaller, all values in the right subtree are larger. This gives O(log n) search, insert, and delete — if the tree is balanced.
# Search in BST — O(log n) average, O(n) worst (skewed)
def search_bst(root: TreeNode | None, target: int) -> TreeNode | None:
if not root or root.val == target:
return root
if target < root.val:
return search_bst(root.left, target)
return search_bst(root.right, target)
# Insert into BST — O(log n) average
def insert_bst(root: TreeNode | None, val: int) -> TreeNode:
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return rootInorder traversal of a BST gives sorted order. This is the key property — if you need the kth smallest element, do inorder and count.
BST Deletion
Deleting from a BST has three cases:
- Leaf node — just remove it
- One child — replace node with its child
- Two children — replace with inorder successor (smallest in right subtree), then delete the successor
LeetCode 450 - Delete Node in a BST
def delete_node(root: TreeNode | None, key: int) -> TreeNode | None:
if not root:
return None
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else:
# Found the node to delete
if not root.left:
return root.right # case 1 & 2
if not root.right:
return root.left # case 2
# Case 3: find inorder successor (min of right subtree)
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val
root.right = delete_node(root.right, successor.val)
return rootBST Validation
A common mistake: checking only that left.val < node.val < right.val. This misses cases where a deeper node violates the BST property relative to an ancestor.
The correct approach passes a valid range down:
LeetCode 98 - Validate Binary Search Tree
def is_valid_bst(root: TreeNode | None) -> bool:
def validate(node, lo=float('-inf'), hi=float('inf')):
if not node:
return True
if node.val <= lo or node.val >= hi:
return False
return (validate(node.left, lo, node.val) and
validate(node.right, node.val, hi))
return validate(root)Each node must be within the range defined by all its ancestors, not just its immediate parent. Python's float('inf') and float('-inf') serve as natural unbounded sentinels.
Balanced vs Unbalanced
A balanced BST has height O(log n). An unbalanced BST (inserting sorted data) degrades to a linked list with height O(n).
Balanced (height 3): Unbalanced (height 5):
4 1
/ \ \
2 6 2
/ \ / \ \
1 3 5 7 3
\
4
\
5Python's standard library doesn't include a self-balancing BST. For ordered operations, use sortedcontainers.SortedList (third-party, pure Python, O(log n) operations) or build on bisect for sorted arrays.
Operation Costs
| Operation | BST (balanced) | BST (worst) | Hash Map (dict) |
|---|---|---|---|
| Search | O(log n) | O(n) | O(1) |
| Insert | O(log n) | O(n) | O(1) |
| Delete | O(log n) | O(n) | O(1) |
| Min/Max | O(log n) | O(n) | O(n) |
| Range query | O(log n + k) | O(n) | O(n) |
| Ordered iteration | O(n) | O(n) | O(n log n)* |
*Dicts need to sort keys for ordered iteration.
BSTs beat hash maps when you need order: min, max, range queries, predecessor/successor, ordered iteration.
When to Use Trees
- Hierarchical data (file systems, DOM, org charts)
- Need sorted order with fast insert/delete → BST
- Need range queries ("all values between 5 and 10") → BST
- Divide-and-conquer algorithms (merge sort is a tree of merges)
- Expression parsing and evaluation
When NOT to Use Trees
- Just need fast lookup by key → dict (simpler, faster)
- Data is flat with no hierarchy → list or dict
- You need O(1) access by index → list
Practice Problems
| Problem | Difficulty | Link |
|---|---|---|
| Maximum Depth of Binary Tree | Easy | LeetCode 104 |
| Invert Binary Tree | Easy | LeetCode 226 |
| Validate Binary Search Tree | Medium | LeetCode 98 |
| Binary Tree Level Order Traversal | Medium | LeetCode 102 |
| Lowest Common Ancestor of a BST | Medium | LeetCode 235 |
| Kth Smallest Element in a BST | Medium | LeetCode 230 |
| Serialize and Deserialize Binary Tree | Hard | LeetCode 297 |
Key Takeaways
- Trees model hierarchy; binary trees have at most two children per node
- Four traversals: inorder (sorted for BST), preorder (serialize), postorder (delete), level-order (BFS)
- Use
collections.dequefor BFS —popleft()is O(1),list.pop(0)is O(n) - Most tree problems are recursive DFS: solve left, solve right, combine
- BSTs give O(log n) search/insert/delete when balanced — but degrade to O(n) when skewed
- BSTs beat dicts when you need order, range queries, or min/max
- Inorder traversal of a BST produces sorted output
- Watch Python's recursion limit (default 1000) for deep trees