The BST Invariant
For every node:
all left descendants < node.val < all right descendants. This applies recursively — not just direct children but ALL descendants.
| Operation | Average | Worst (unbalanced) |
|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| In-order traversal | O(n) — gives sorted output! |
Validate BST — use min/max bounds
Check node.val > min AND node.val < max (not just parent comparison). Pass bounds down: left subtree gets upper bound = node.val, right subtree gets lower bound = node.val.
# Validate BST
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
if not root: return True
if not (lo < root.val < hi): return False
return (is_valid_bst(root.left, lo, root.val) and
is_valid_bst(root.right, root.val, hi))
DFS Templates
# Max depth — post-order (bottom-up)
def max_depth(root):
if not root: return 0
left = max_depth(root.left)
right = max_depth(root.right)
return 1 + max(left, right)
# Diameter — track global max
def diameter(root):
res = [0]
def dfs(node):
if not node: return 0
l, r = dfs(node.left), dfs(node.right)
res[0] = max(res[0], l + r)
return 1 + max(l, r)
dfs(root); return res[0]
# LCA of Binary Tree
def lca(root, p, q):
if not root or root in (p, q): return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
return root if left and right else left or right