Trees
Use when: problems on binary trees, BSTs, path sums, LCA, serialize/deserialize, diameter.
Traversals
# Inorder (left → root → right) — gives sorted order for BST
def inorder(root):
if not root: return
inorder(root.left)
visit(root)
inorder(root.right)
# Preorder (root → left → right) — useful for serialization
def preorder(root):
if not root: return
visit(root)
preorder(root.left)
preorder(root.right)
# Postorder (left → right → root) — useful for bottom-up computation
def postorder(root):
if not root: return
postorder(root.left)
postorder(root.right)
visit(root)Common DFS Pattern (return value up the tree)
Most tree problems can be solved by returning computed values from children up to parent.
def dfs(node):
if not node:
return <base_case>
left = dfs(node.left)
right = dfs(node.right)
# compute answer using node.val, left, right
return <value_to_pass_up>BST Properties
- Inorder traversal yields sorted values
- For any node: all left descendants < node.val < all right descendants
- Search, insert, delete: O(h) where h = height
LCA Pattern
def lca(root, p, q):
if not root or root == p or root == q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root # p and q split across this node
return left or right