1.7 Trees

Deep Dive: Why Recursion is the Language of Trees

Beginner tip: A tree is like an upside-down family tree. The top node is the "root" (like a great-grandparent). Each node can have "children" below it. The bottom nodes with no children are called "leaves." Almost every tree problem is solved by asking: "What does each node need to know from its children?" (bottom-up) or "What does each node need to tell its children?" (top-down).

The Depth Insight (Bottom-Up Thinking)

How does maxDepth actually work? Trace this tree:

        3
       / \
      9   20
         / \
        15   7

maxDepth(3)
  maxDepth(9)
    maxDepth(None) -> 0       left
    maxDepth(None) -> 0       right
    return 1 + max(0, 0) = 1
  maxDepth(20)
    maxDepth(15)
      return 1 + max(0, 0) = 1
    maxDepth(7)
      return 1 + max(0, 0) = 1
    return 1 + max(1, 1) = 2
  return 1 + max(1, 2) = 3       <-- ANSWER

The pattern: Leaves answer "1" (base). Each parent combines children's answers. Information flows UP from leaves to root. This is post-order thinking.

The BST Validation Insight (Top-Down Thinking)

For isValidBST, you pass constraints DOWN:

        5         range: (-inf, +inf)
       / \
      3   7       3's range: (-inf, 5)  |  7's range: (5, +inf)
     / \
    1   4         1's range: (-inf, 3)  |  4's range: (3, 5)  -- VALID

If node 4 were 6 instead: range (3, 5) violated! Note: checking only left.val < root.val misses this.

The pattern: Parent tells children what's allowed. Information flows DOWN from root to leaves. This is pre-order thinking.

When to Use Which Traversal

Need sorted output from BST?  -> Inorder (L, Root, R)
Need to process root first?   -> Preorder (Root, L, R)
Need children's answers first? -> Postorder (L, R, Root)
Need level-by-level info?     -> BFS with queue

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Trees

Why Trees Exist

Need: Hierarchical relationships + efficient search. Key insight: Trees give O(log n) search/insert/delete when balanced.

The Tree Mindset

Almost every tree problem is solved by recursion. The question is: what do I compute at each node, and what do I pass up/down?

Two Directions of Information Flow

TOP-DOWN (passing info FROM parent TO children):
  "Is this BST valid?" -> Pass allowed range (min, max) down
  "Root-to-leaf path sum" -> Pass running sum down

BOTTOM-UP (collecting info FROM children TO parent):
  "What's the height?" -> Children return height, parent takes max + 1
  "What's the diameter?" -> Children return depth, parent computes through-me path
  "Maximum path sum" -> Children return best single-branch sum

The Four Traversals and When to Use Each

Traversal	Order	When to Use
Inorder (L, Root, R)	BST gives sorted order	Kth smallest, validate BST
Preorder (Root, L, R)	Process root first	Serialize tree, copy tree
Postorder (L, R, Root)	Process children first	Delete tree, compute heights, path sums
Level Order (BFS)	Level by level	Right side view, zigzag, min depth

BST-Specific Thinking

BST Property: left < root < right (for ALL descendants, not just children)

- "Search for value" -> Go left if smaller, right if larger: O(log n)
- "Validate BST" -> Pass (min, max) range; each node must be within range
- "Kth smallest" -> Inorder traversal gives sorted order; stop at k
- "LCA in BST" -> If both values < node, go left. Both > node, go right. Else, node IS LCA.

When You See a Tree Problem, Ask Yourself

1. Is this a TRAVERSAL? Which order? Inorder/Preorder/Postorder/BFS?
2. Do I need TOP-DOWN info (pass range/sum down) or BOTTOM-UP info (collect height/count up)?
3. Is it a BST? Can I exploit the sorted property?
4. Do I need LEVEL information? -> BFS with queue
5. Am I modifying the tree or just reading it?

Common Mistakes

• Confusing "height" (bottom-up, leaves = 0) vs "depth" (top-down, root = 0)
• BST validation: checking only left.val < root.val is WRONG. Must check ALL descendants.
• Forgetting None base case in recursion: if root is None: return ...
• Not considering the "through parent" path in diameter/max path sum problems

Problems

#	Problem	Difficulty	Pattern	Status
1	Maximum Depth of Binary Tree	Easy	DFS recursion	[ ]
2	Invert Binary Tree	Easy	Recursive swap	[ ]
3	Same Tree / Subtree Check	Easy	Simultaneous traversal	[ ]
4	Binary Tree Level Order Traversal	Medium	BFS with queue	[ ]
5	Validate BST	Medium	Inorder / range passing	[ ]
6	Lowest Common Ancestor	Medium	DFS with path tracking	[ ]
7	Binary Tree Maximum Path Sum	Hard	Post-order DP	[ ]
8	Serialize/Deserialize Binary Tree	Hard	Preorder + null markers	[ ]
9	Diameter of Binary Tree	Easy	DFS height tracking	[ ]
10	Kth Smallest Element in BST	Medium	Inorder traversal	[ ]
11	Construct Tree from Preorder + Inorder	Medium	Divide & Conquer	[ ]
12	Binary Tree Right Side View	Medium	BFS / DFS rightmost	[ ]

Notes