Week 6: Binary Trees & BSTs

1. Overview

Welcome to Week 6! It is time to leave linear data structures (arrays, strings, linked lists) behind and step into the multi-dimensional world of Hierarchical Data. This week focuses on Binary Trees and Binary Search Trees (BSTs).

Trees are the underlying architecture for databases (B-Trees), file systems, DOM rendering, and decision engines. You will learn the two primary ways to traverse hierarchical data: plunging deep into the leaves (DFS) and exploring layer by layer (BFS).

Goals for this week:

• Understand Tree terminology: Root, Leaf, Height, Depth, and Ancestor.
• Master Depth-First Search (Pre-order, In-order, Post-order) using Recursion.
• Master Breadth-First Search (Level-order) using a Queue.
• Understand the strict mathematical properties of a Binary Search Tree.

Knowledge You Need Before Starting

• Week 5 stack/queue mental models (LIFO and FIFO behavior).
• Basic recursion traceability from linked-list pointer practice.
• Comfort with class/object modeling for TreeNode.
• Confidence with null checks and branching edge cases.

---

2. Theory & Fundamentals

2.1 Mental Model: Why Trees Exist

Think of real-world hierarchies:

• Company org chart: CEO → VPs → Managers → Employees
• File system: Root / → home → user → documents → file.txt
• Decision tree: "Is it raining?" → Yes → "Bring umbrella" / No → "Don't bring umbrella"

These relationships are naturally parent-child, not sequential. A tree captures this perfectly: one root, many branches, and leaves at the end.

Linear (Array):   [A] → [B] → [C] → [D]
                   ↑ can only go forward/backward

Hierarchical (Tree):
                      A (root)
                     / \
                    B   C
                   /     \
                  D       E (leaves)
                   ↑ can branch, explore multiple paths

Why not just use an array of objects with parent IDs? You could, but then every operation (search, insert, delete) requires scanning the entire array. A tree gives you O(\log N) operations when balanced.

---

2.2 Tree Terminology (Critical for Interviews)

                1 (root) ← depth 0, height 3
               / \
              2   3      ← depth 1
             / \   \
            4   5   6    ← depth 2
           /
          7              ← depth 3 (leaf), this is the deepest leaf

Term	Definition	Example from tree above
Root	The topmost node with no parent	1
Leaf	A node with no children	5, 3, 6, 7
Parent	A node with children	1 is parent of 2 and 3
Child	Direct descendant of a node	2 and 3 are children of 1
Ancestor	Any node on the path from root to this node	For 7: ancestors are 4, 2, 1
Descendant	Any node in the subtree rooted at this node	For 2: descendants are 4, 5, 7
Sibling	Nodes with the same parent	2 and 3 are siblings
Depth	Distance from root to this node	Depth of 4 is 2
Height	Distance from this node to its deepest leaf	Height of 2 is 2, height of 1 is 3
Level	All nodes at the same depth	Level 2 = [4, 5, 6]

Critical formulas to memorize:

• Height of tree = depth of deepest leaf
• Number of nodes in a perfect binary tree of height h = 2^(h+1) - 1
• Maximum number of nodes at level L = 2^L
• Height of a balanced binary tree with N nodes = O(\log N)
• Height of a skewed binary tree with N nodes = O(N) (degenerate into a linked list)

---

2.3 Binary Trees: Structure and Properties

A Binary Tree means each node has at most 2 children (can have 0, 1, or 2).

Valid Binary Tree:
       5
      / \
     3   8
    /
   1

Still Valid (not full, but binary):
       5
      /
     3
    /
   1   ← this is just a linked list, but still a "binary tree"

Types of Binary Trees:

Type	Definition	Example
Full	Every node has 0 or 2 children (never just 1)	All internal nodes have both kids
Complete	All levels fully filled except possibly the last, which fills left-to-right	Heap structure
Perfect	All internal nodes have 2 children AND all leaves are at the same level	2^(h+1) - 1 nodes
Balanced	Height is O(\log N) where N is number of nodes	AVL, Red-Black trees
Skewed	Every node has at most one child (essentially a linked list)	Worst-case BST

---

2.4 Recursion: The Natural Way to Think About Trees

Why recursion dominates tree problems:

A tree is a recursive data structure. Every subtree is itself a tree. So tree problems naturally decompose into:

1. Base case: What do I do at null or a leaf?
2. Recursive case: Solve for left child, solve for right child, combine the results.

height(tree) = ???

Recursive insight:
height(tree) = 1 + max(height(left_subtree), height(right_subtree))

Base case:
height(null) = 0

The Call Stack = Your Explorer's Backpack

When you write maxDepth(root.left), Java pushes a new stack frame. Think of it like:

• You're standing at node 5.
• You tell your left-hand clone: "Go explore the left subtree, report back with its depth."
• While waiting, you tell your right-hand clone: "Go explore the right subtree."
• Once both return, you compute: 1 + max(leftDepth, rightDepth).

The call stack tracks all these "clones" waiting for their subtrees to report back.

Stack Overflow Risk in Java:

The JVM's default stack size is typically ~1MB, which allows about 5,000–10,000 nested calls depending on local variable size. A deeply skewed tree with 100,000 nodes will crash with StackOverflowError.

// This will crash on a skewed tree with 100,000 nodes
public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Solution: For very deep trees, convert to iterative using an explicit Stack<TreeNode>.

---

2.5 DFS vs. BFS: When to Use Which

Tree:
       1
      / \
     2   3
    / \
   4   5

DFS Pre-order (Root → Left → Right):  1, 2, 4, 5, 3
DFS In-order  (Left → Root → Right):  4, 2, 5, 1, 3
DFS Post-order(Left → Right → Root):  4, 5, 2, 3, 1

BFS Level-order:  1, 2, 3, 4, 5

Question Type	Use DFS or BFS?	Why?
"Find the depth/height of the tree"	DFS (any order)	Natural recursion on subtrees
"Is this tree symmetric?"	DFS Pre-order	Mirror-check left vs right
"Print nodes level by level"	BFS	Need to group by level
"Find the shortest path to a leaf"	BFS	BFS finds shortest path in unweighted trees
"Right side view" (rightmost node per level)	BFS	Process level by level
"Validate BST"	DFS In-order	In-order gives sorted output
"Sum all root-to-leaf paths"	DFS Pre-order	Build path as you go down
"Find diameter (longest path)"	DFS Post-order	Need child results before computing parent
"Lowest common ancestor"	DFS Post-order	Bubble up found nodes
"Serialize/Deserialize tree"	DFS Pre-order	Need root first to rebuild

Memory comparison:

	DFS (Recursive)	BFS (Queue)
Space	O(H) call stack (H = height)	O(W) queue (W = max width)
Best case	Balanced tree: O(\log N)	Skewed tree: O(1)
Worst case	Skewed tree: O(N)	Perfect tree: O(N/2) = O(N)

For a perfect binary tree, BFS uses more space because the last level has N/2 nodes all in the queue at once. For a skewed tree, DFS uses more space because the call stack is N deep.

---

2.6 The Three DFS Traversals: What They Mean

Pre-order (Root → Left → Right):

• "Process root before children"
• Use when: Creating a copy, serializing, printing tree structure
• Think: "I need to know the parent before I can process children"

void preorder(TreeNode node) {
    if (node == null) return;
    process(node);           // ← Root first
    preorder(node.left);     // ← Then left
    preorder(node.right);    // ← Then right
}

In-order (Left → Root → Right):

• "Process root between children"
• Use when: BST problems requiring sorted order
• Think: "I'm sweeping left to right across the tree"

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);      // ← Left first
    process(node);           // ← Root in the middle
    inorder(node.right);     // ← Right last
}

Post-order (Left → Right → Root):

• "Process root after children"
• Use when: Calculating properties that depend on child results (height, diameter, deleting nodes)
• Think: "I can't know anything about this node until I've explored its children"

void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);    // ← Left first
    postorder(node.right);   // ← Right second
    process(node);           // ← Root last (after getting child results)
}

---

2.7 Binary Search Trees: The Sorted Superpower

A Binary Search Tree (BST) is a binary tree where:

1. All values in the left subtree < current node
2. All values in the right subtree > current node
3. No duplicate values (standard convention)
4. Both left and right subtrees are also BSTs (recursive property)

Valid BST:
       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

WHY? At node 8:
- Left subtree [1,3,4,6,7] are ALL < 8 ✅
- Right subtree [10,13,14] are ALL > 8 ✅

Invalid BST:
       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   9 13  ← 9 is in right subtree of 8 but < 8 ❌

The Key Insight: In-order traversal of a BST gives sorted order

In-order of valid BST above: 1, 3, 4, 6, 7, 8, 10, 13, 14  ← Sorted! ✅

Operations on a balanced BST:

Operation	Time	Why
Search	O(\log N)	Eliminate half the tree each step
Insert	O(\log N)	Search for position, attach
Delete	O(\log N)	Find node, rearrange pointers
Find min/max	O(\log N)	Go all the way left/right
Find successor	O(\log N)	Smallest in right subtree

Degenerate case (skewed tree): All operations degrade to O(N) — the tree is just a linked list.

Skewed BST (worst case):
1
 \
  2
   \
    3
     \
      4  ← search for 4 takes O(N) steps, not O(log N)

Solution: Self-balancing trees like AVL or Red-Black trees guarantee O(\log N) height through rotations.

---

2.8 Common BST Validation Mistake

WRONG approach — only checking immediate children:

// ❌ This is INCORRECT — fails on the example below
boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (root.left != null && root.left.val >= root.val) return false;
    if (root.right != null && root.right.val <= root.val) return false;
    return isValidBST(root.left) && isValidBST(root.right);
}

This fails on:

    10
   /  \
  5    15
      /  \
     6   20   ← 6 < 15 ✅ but 6 < 10 ❌ (violates BST: right subtree must be > 10)

CORRECT approach — passing valid range bounds:

Every node must fall within a range (min, max). As you go left, update max. As you go right, update min.

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) &&    // left: shrink upper bound
           validate(node.right, node.val, max);     // right: shrink lower bound
}

---

3. Code Templates (Java)

The Standard TreeNode Class

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Template 1: BFS / Level-Order Traversal

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // Critical: lock in current level size
        List<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode curr = queue.poll();
            currentLevel.add(curr.val);

            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }
        result.add(currentLevel);
    }
    return result;
}

Why levelSize matters: Without it, you'd mix nodes from different levels in the same iteration. By locking in the size, you process exactly one level per outer loop iteration.

Variant: Right Side View

// Return the rightmost node of each level
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        TreeNode rightmost = null;

        for (int i = 0; i < levelSize; i++) {
            TreeNode curr = queue.poll();
            rightmost = curr; // last node polled = rightmost

            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }
        result.add(rightmost.val);
    }
    return result;
}

Template 2: DFS Pre-order (Recursive)

// Use for: copying, serializing, building paths
public void preorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    result.add(root.val);       // Process root first
    preorder(root.left, result);
    preorder(root.right, result);
}

Template 3: DFS In-order (Recursive)

// Use for: BST problems requiring sorted order
public void inorder(TreeNode root, List<Integer> result) {
    if (root == null) return;
    inorder(root.left, result);
    result.add(root.val);        // Process root in the middle
    inorder(root.right, result);
}

Template 4: DFS Post-order (Recursive)

// Use for: height, diameter, deletion (need child results first)
public int maxDepth(TreeNode root) {
    if (root == null) return 0;  // Base case

    int leftDepth = maxDepth(root.left);   // Get left result
    int rightDepth = maxDepth(root.right); // Get right result

    return 1 + Math.max(leftDepth, rightDepth); // Combine
}

Template 5: DFS Iterative (Using Stack)

// Pre-order iterative (useful for deep trees to avoid StackOverflowError)
public List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode curr = stack.pop();
        result.add(curr.val);

        // Push right first so left is processed first (stack is LIFO)
        if (curr.right != null) stack.push(curr.right);
        if (curr.left != null) stack.push(curr.left);
    }
    return result;
}

Template 6: BST Search

// Iterative (preferred for BST — no call stack overhead)
public TreeNode searchBST(TreeNode root, int target) {
    TreeNode curr = root;
    while (curr != null) {
        if (target == curr.val) return curr;
        else if (target < curr.val) curr = curr.left;
        else curr = curr.right;
    }
    return null;
}

Template 7: BST Insert

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);

    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

Template 8: BST Validation (Range Bounds)

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;

    return validate(node.left, min, node.val) &&
           validate(node.right, node.val, max);
}

Template 9: Path Sum (Root to Leaf)

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;

    // Leaf node check
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }

    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

Template 10: Lowest Common Ancestor (LCA)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // If both sides found a target, current root is the LCA
    if (left != null && right != null) return root;

    // Otherwise return whichever side found something
    return left != null ? left : right;
}

Template 11: Tree Diameter (Longest Path)

class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return maxDiameter;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        // Diameter through this node = left height + right height
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        return 1 + Math.max(leftHeight, rightHeight);
    }
}

---

4. Problem-Solving Framework

Step 1 — Clarify (2 minutes)

Ask these questions:

• Is this a binary tree or specifically a BST? (BST unlocks in-order sorted optimization)
• Can node values be negative? Zero? Duplicates?
• Can the tree be empty (root == null)?
• For path problems: Does the path have to start at root and end at a leaf?
• For BST: Are values unique?
• Memory constraints: Can I use O(N) space or must it be O(H)?

Step 2 — Draw the Tree

Always draw at least two test cases:

1. A balanced tree
2. A skewed tree (or other edge case: single node, empty, all left children, etc.)

Example: "Find max depth"

Balanced:         Skewed:
    1               1
   / \               \
  2   3               2
 /                     \
4                       3

Expected: 3          Expected: 3

Step 3 — Identify Traversal Type

Signal	Traversal
"Level by level", "Shortest path", "Right side view"	BFS
"Sorted", "K-th smallest" (in BST)	DFS In-order
"Copy", "Serialize", "Path from root"	DFS Pre-order
"Height", "Diameter", "Validate", "Bottom-up calculation"	DFS Post-order
"Symmetric", "Mirror"	DFS Pre-order (with custom logic)

Step 4 — Write the Base Case First

The base case is the foundation of your recursion. Always write it before the recursive calls.

// Base case for most tree problems:
if (root == null) return /* appropriate value */;
    // return 0 for height/count
    // return null for finding a node
    // return true for validation (empty trees are valid)
    // return false for path sum (no path exists)

Step 5 — Think "What Do I Need From My Children?"

This is the key to post-order thinking:

• Height: I need the height of left and right, then return 1 + max(left, right)
• Balanced: I need the height of both sides and whether they're balanced. If heights differ by more than 1, return false.
• Diameter: I need the height of both sides. The diameter through this node is leftHeight + rightHeight.

Step 6 — Code and Test

Walk through your code manually with the drawn examples. Check:

• Does it handle root == null?
• Does it handle a single-node tree?
• Does it correctly combine left and right results?

---

5. Pattern Recognition Guide

Signal → Pattern Mapping

What the problem says	Pattern	Key technique
"Print/return nodes level by level"	BFS	Queue + levelSize loop
"Right side view", "Zigzag level order"	BFS	Track level, maybe reverse
"Shortest path to a leaf"	BFS	BFS finds shortest path
"Is tree symmetric?"	DFS Pre-order	Recursively compare left.left vs right.right
"Is tree balanced?"	DFS Post-order	Need child heights to check balance
"Find diameter"	DFS Post-order	Track max path through each node
"Validate BST"	DFS In-order or Range Bounds	In-order should be sorted
"K-th smallest in BST"	DFS In-order	Stop at K-th element
"Lowest common ancestor"	DFS Post-order	Bubble up found nodes
"Path sum", "All paths"	DFS Pre-order	Build path going down
"Serialize/Deserialize"	DFS Pre-order	Process root before children
"Invert tree"	DFS Pre-order	Swap children before recursing
"Delete node in BST"	DFS	3 cases: no children, 1 child, 2 children
"Construct from traversals"	DFS	Use indices to split left/right

---

Detailed Recognition Walkthroughs

Recognizing Post-Order (LC 543 — Diameter)

When you see: "Find the longest path between any two nodes"

1. "The longest path through a node = left height + right height."
2. "But I can't compute this until I know the heights of my children."
3. "I need to calculate height for every node and track the max diameter."
4. Post-order: get left height, get right height, then compute diameter through current node.

Recognizing BFS (LC 102 — Level Order)

When you see: "Return nodes grouped by level"

1. "I need to process all nodes at depth 0, then depth 1, then depth 2, etc."
2. "DFS doesn't naturally group by level — it goes deep first."
3. "BFS with a queue naturally processes level by level."
4. Use the levelSize = queue.size() trick to avoid mixing levels.

Recognizing BST In-Order (LC 230 — K-th Smallest)

When you see: "Find the K-th smallest element in a BST"

1. "BST in-order traversal gives sorted order."
2. "Just do in-order and stop at the K-th element."
3. Use a counter variable to track how many nodes processed.

Recognizing Range Validation (LC 98 — Validate BST)

When you see: "Determine if a tree is a valid BST"

1. "Checking only immediate children is not enough."
2. "Every node must satisfy: min < node.val < max."
3. "As I recurse left, the max shrinks to current node's value."
4. "As I recurse right, the min grows to current node's value."

---

6. Common Mistakes & How to Avoid Them

Mistake 1: Forgetting the Null Check

// ❌ NullPointerException when root is null
public int maxDepth(TreeNode root) {
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// ✅ Always check null first
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Mistake 2: Confusing Pre-order vs. Post-order

// Problem: Find height

// ❌ WRONG — pre-order processes root before getting child results
public int height(TreeNode root) {
    if (root == null) return 0;
    int h = 1; // trying to compute height before knowing child heights?
    // How can we know the height without asking children first?
}

// ✅ CORRECT — post-order gets child results first
public int height(TreeNode root) {
    if (root == null) return 0;
    int left = height(root.left);   // get left child's answer
    int right = height(root.right); // get right child's answer
    return 1 + Math.max(left, right); // then compute own answer
}

Mistake 3: Not Using the levelSize Trick in BFS

// ❌ WRONG — mixes levels together
while (!queue.isEmpty()) {
    TreeNode curr = queue.poll();
    result.add(curr.val); // all nodes end up in one big list, not grouped by level
    if (curr.left != null) queue.offer(curr.left);
    if (curr.right != null) queue.offer(curr.right);
}

// ✅ CORRECT — lock in level size
while (!queue.isEmpty()) {
    int levelSize = queue.size();
    List<Integer> level = new ArrayList<>();
    for (int i = 0; i < levelSize; i++) {
        TreeNode curr = queue.poll();
        level.add(curr.val);
        if (curr.left != null) queue.offer(curr.left);
        if (curr.right != null) queue.offer(curr.right);
    }
    result.add(level); // each level is separate
}

Mistake 4: Only Checking Immediate Children in BST Validation

// ❌ WRONG — fails when a right grandchild is < root
public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (root.left != null && root.left.val >= root.val) return false;
    if (root.right != null && root.right.val <= root.val) return false;
    return isValidBST(root.left) && isValidBST(root.right);
}

// ✅ CORRECT — pass min/max bounds down
public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) &&
           validate(node.right, node.val, max);
}

Mistake 5: Forgetting to Handle Leaf Nodes in Path Problems

// Problem: Path sum from root to leaf

// ❌ WRONG — considers any node, not just leaves
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    if (root.val == sum) return true; // ← what if this is not a leaf?
    return hasPathSum(root.left, sum - root.val) || ...
}

// ✅ CORRECT — check that it's a leaf
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    // Only check sum at a LEAF node
    if (root.left == null && root.right == null) {
        return root.val == sum;
    }
    int remaining = sum - root.val;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

Mistake 6: Modifying Tree Structure During Traversal

// ❌ DANGEROUS — deleting nodes while recursing can lose references
public void deleteNodes(TreeNode root) {
    if (root == null) return;
    if (shouldDelete(root.left)) root.left = null; // might lose entire subtree!
    deleteNodes(root.left);
    // ...
}

// ✅ SAFE — process children first (post-order), then decide on current
public TreeNode deleteNodes(TreeNode root) {
    if (root == null) return null;
    root.left = deleteNodes(root.left);   // clean left first
    root.right = deleteNodes(root.right); // clean right first
    if (shouldDelete(root)) return null;  // then decide on current
    return root;
}

---

7. Worked Examples

Example 1: LeetCode 226 — Invert Binary Tree

Thinking process:

1. "Inverting means swapping left and right at every node."
2. "I should do this top-down (pre-order) so the swap happens before recursing."

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        // Swap the children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // Recursively invert the subtrees
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

Dry run for tree:

Before:   1          After:   1
         / \                 / \
        2   3               3   2

Step 1: At node 1, swap 2 and 3 → root.left=3, root.right=2
Step 2: Recurse on 3 (no children, return)
Step 3: Recurse on 2 (no children, return)
Result: ✅

Time: O(N). Space: O(H) call stack.

---

Example 2: LeetCode 98 — Validate Binary Search Tree

Thinking process:

1. "Checking only immediate children doesn't work (see Section 2.8)."
2. "Every node must satisfy min < node.val < max."
3. "As I go left, max becomes node.val. As I go right, min becomes node.val."

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true; // Empty trees are valid

        if (node.val <= min || node.val >= max) return false;

        // Left: upper bound shrinks to node.val
        // Right: lower bound grows to node.val
        return validate(node.left, min, node.val) &&
               validate(node.right, node.val, max);
    }
}

Dry run:

Tree:    8              Call stack:
        / \
       3   10           validate(8, -∞, +∞)
      / \    \            8 is in (-∞, +∞) ✅
     1   6    14          ├─ validate(3, -∞, 8)
        / \   /           │    3 is in (-∞, 8) ✅
       4   7 13           │    ├─ validate(1, -∞, 3) → 1 in (-∞, 3) ✅
                          │    └─ validate(6, 3, 8)
                          │         6 is in (3, 8) ✅
                          │         ├─ validate(4, 3, 6) → 4 in (3, 6) ✅
                          │         └─ validate(7, 6, 8) → 7 in (6, 8) ✅
                          └─ validate(10, 8, +∞)
                               10 is in (8, +∞) ✅
                               └─ validate(14, 10, +∞)
                                    14 is in (10, +∞) ✅
                                    └─ validate(13, 10, 14) → 13 in (10, 14) ✅

Result: true ✅

Time: O(N). Space: O(H).

---

Example 3: LeetCode 102 — Binary Tree Level Order Traversal

Thinking process:

1. "Need to group nodes by level → BFS."
2. "Use queue + lock in levelSize each iteration."

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode curr = queue.poll();
                currentLevel.add(curr.val);

                if (curr.left != null) queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
            result.add(currentLevel);
        }
        return result;
    }
}

Dry run:

Tree:     3
         / \
        9  20
          /  \
         15   7

Initial: queue = [3], result = []
Level 0: levelSize=1, poll(3), add 9,20 to queue → currentLevel=[3] → result=[[3]]
Level 1: levelSize=2, poll(9), poll(20), add 15,7 → currentLevel=[9,20] → result=[[3],[9,20]]
Level 2: levelSize=2, poll(15), poll(7) → currentLevel=[15,7] → result=[[3],[9,20],[15,7]]

Result: [[3],[9,20],[15,7]] ✅

Time: O(N). Space: O(W) where W is max width.

---

Example 4: LeetCode 543 — Diameter of Binary Tree

Thinking process:

1. "Diameter through a node = left height + right height."
2. "I need to compute height for every node → post-order."
3. "Track a global max diameter as I go."

class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return maxDiameter;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;

        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        // Diameter through this node
        int diameterThroughNode = leftHeight + rightHeight;
        maxDiameter = Math.max(maxDiameter, diameterThroughNode);

        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Dry run:

Tree:     1
         / \
        2   3
       / \
      4   5

height(4): returns 1
height(5): returns 1
height(2): leftHeight=1, rightHeight=1, diameter=2, maxDiameter=2, returns 2
height(3): returns 1
height(1): leftHeight=2, rightHeight=1, diameter=3, maxDiameter=3, returns 3

Result: 3 ✅ (path: 4 → 2 → 1 → 3, length 3 edges)

Time: O(N). Space: O(H).

---

Example 5: LeetCode 236 — Lowest Common Ancestor (LCA)

Thinking process:

1. "If left subtree has one target and right has the other, current node is the LCA."
2. "Use post-order: get results from children first, then decide at parent."

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root; // found one of the targets

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // Both children returned a target → current node is the LCA
        if (left != null && right != null) return root;

        // Only one side found something → propagate it up
        return left != null ? left : right;
    }
}

Time: O(N). Space: O(H).

---

8. Decision Tree: Which Tree Pattern?

What does the problem need?
├── Group nodes by level?
│   └── YES → BFS with levelSize loop
│
├── Sorted order from BST?
│   └── YES → DFS In-order
│
├── Need child results before computing parent?
│   └── YES → DFS Post-order
│       Examples: height, diameter, balanced, LCA
│
├── Build something top-down (path, copy, serialize)?
│   └── YES → DFS Pre-order
│
├── Check structural property (symmetric, invert)?
│   └── YES → DFS Pre-order with custom logic
│
└── Validate BST?
    └── Use range bounds OR in-order check for sorted

---

9. Complexity Cheat Sheet

Operation	Time	Space
Traverse full tree (DFS/BFS)	O(N)	DFS: O(H), BFS: O(W)
Find height/depth	O(N)	O(H) call stack
Level order traversal	O(N)	O(W) queue (W = max width)
BST search (balanced)	O(\log N)	O(1) iterative, O(\log N) recursive
BST search (skewed)	O(N)	O(1) iterative, O(N) recursive
BST insert/delete (balanced)	O(\log N)	O(\log N) recursive
Validate BST	O(N)	O(H)
LCA	O(N)	O(H)
Serialize/Deserialize	O(N)	O(N) string, O(H) call stack
Count nodes in perfect tree	O(\log^2 N)*	O(\log N)

*Count nodes in perfect tree: Check if left and right heights are equal. If yes, use formula 2^h - 1. If no, recurse.

---

10. 7-Day Practice Plan (21 Problems)

Day 1: DFS Fundamentals

1. Invert Binary Tree (LC 226) — Pre-order swap
2. Maximum Depth of Binary Tree (LC 104) — Post-order height
3. Same Tree (LC 100) — Pre-order structural check

Day 2: BFS / Level-Order Traversal 4. Binary Tree Level Order Traversal (LC 102) — Classic BFS 5. Binary Tree Right Side View (LC 199) — BFS variant 6. Binary Tree Zigzag Level Order Traversal (LC 103) — BFS + reverse

Day 3: Tree Properties & Post-Order Processing 7. Diameter of Binary Tree (LC 543) ⭐ — Global max tracking 8. Balanced Binary Tree (LC 110) — Height + balance check 9. Symmetric Tree (LC 101) — Pre-order mirror check

Day 4: Path Finding & Backtracking 10. Path Sum (LC 112) — Root to leaf path 11. Path Sum II (LC 113) — Collect all paths 12. Sum Root to Leaf Numbers (LC 129) — Build number as you go

Day 5: BST Fundamentals 13. Search in a Binary Search Tree (LC 700) — BST property 14. Insert into a Binary Search Tree (LC 701) — Recursive insert 15. Lowest Common Ancestor of a BST (LC 235) — BST-specific LCA

Day 6: Advanced BST & Validation 16. Validate Binary Search Tree (LC 98) ⭐ — Range bounds 17. Kth Smallest Element in a BST (LC 230) — In-order counting 18. Delete Node in a BST (LC 450) — 3 cases (hard pointer work)

Day 7: Construction & Advanced 19. Construct Binary Tree from Preorder and Inorder (LC 105) — Index splitting 20. Flatten Binary Tree to Linked List (LC 114) — Pre-order flattening 21. Subtree of Another Tree (LC 572) — Recursive structure check

---

11. Mock Interview Module

Problem: The Distributed Version Control Merge-Base

Context: You are building the backend for a new internal Git-like version control system. Commits form a strictly branching Binary Tree (ignoring complex DAG merges). When a developer wants to merge two branches, the system must find the "merge-base" — the most recent common ancestor commit.

Question: Write public CommitNode findMergeBase(CommitNode root, CommitNode branchA, CommitNode branchB) that returns the lowest common ancestor.

(Assume CommitNode = TreeNode. All node values are unique. Both branchA and branchB are guaranteed to exist.)

---

Step 1: Clarifying Questions & Expected Answers

Candidate asks	Interviewer answers	Why it matters
"Do nodes have a parent pointer?"	No, only left/right	Rules out bottom-up traversal
"Can a node be its own ancestor?"	Yes, if branchA is parent of branchB	Edge case handling
"Are both branches guaranteed to exist?"	Yes	No need for null checks on p/q
"Is the tree a BST?"	No, just a binary tree	Can't use BST optimization

---

Step 2: Brute Force Solution

// Time: O(N), Space: O(N) for path arrays
// Find path to branchA, find path to branchB, compare paths until they diverge
public CommitNode findMergeBase(CommitNode root, CommitNode a, CommitNode b) {
    List<CommitNode> pathA = new ArrayList<>();
    List<CommitNode> pathB = new ArrayList<>();
    findPath(root, a, pathA);
    findPath(root, b, pathB);
    
    CommitNode lca = null;
    for (int i = 0; i < Math.min(pathA.size(), pathB.size()); i++) {
        if (pathA.get(i) == pathB.get(i)) lca = pathA.get(i);
        else break;
    }
    return lca;
}

private boolean findPath(CommitNode node, CommitNode target, List<CommitNode> path) {
    if (node == null) return false;
    path.add(node);
    if (node == target) return true;
    if (findPath(node.left, target, path) || findPath(node.right, target, path)) {
        return true;
    }
    path.remove(path.size() - 1); // backtrack
    return false;
}

Explain: "This works but requires two full tree traversals and O(N) space for paths. Can we do it in one pass?"

---

Step 3: Optimized Solution (DFS Post-Order)

// Time: O(N), Space: O(H) call stack
public CommitNode findMergeBase(CommitNode root, CommitNode branchA, CommitNode branchB) {
    // Base cases
    if (root == null) return null;
    if (root == branchA || root == branchB) return root; // found a target

    // Recursively search left and right subtrees
    CommitNode leftResult = findMergeBase(root.left, branchA, branchB);
    CommitNode rightResult = findMergeBase(root.right, branchA, branchB);

    // If both sides found a target, current node is the LCA
    if (leftResult != null && rightResult != null) return root;

    // Otherwise return whichever side found something
    return leftResult != null ? leftResult : rightResult;
}

Walk through the logic:

Tree:        3
           /   \
          5     1
         / \   / \
        6   2 0   8
           / \
          7   4

Find LCA of 5 and 1:

Call stack (simplified):
lca(3, 5, 1):
  leftResult = lca(5, 5, 1) → returns 5 (found branchA)
  rightResult = lca(1, 5, 1) → returns 1 (found branchB)
  Both non-null → return 3 ✅

Find LCA of 7 and 4:
lca(3, 7, 4):
  leftResult = lca(5, 7, 4):
    leftResult = lca(6, 7, 4) → null
    rightResult = lca(2, 7, 4):
      leftResult = lca(7, 7, 4) → returns 7
      rightResult = lca(4, 7, 4) → returns 4
      Both non-null → return 2 ✅
    return 2
  return 2
  rightResult = lca(1, 7, 4) → null
  return 2 ✅

Time: O(N). Space: O(H) call stack.

---

Step 4: Follow-up Questions

Q1: "What if this was a BST based on commit timestamps?"

Expected answer: "If it's a BST, I can optimize using the BST property:

• If both nodes are smaller than root, LCA is in left subtree.
• If both nodes are larger than root, LCA is in right subtree.
• Otherwise, current node is the LCA (split point).

This reduces average case from O(N) to O(\log N) in a balanced BST, and I can do it iteratively for O(1) space."

public CommitNode findMergeBaseBST(CommitNode root, CommitNode p, CommitNode q) {
    CommitNode curr = root;
    while (curr != null) {
        if (p.val < curr.val && q.val < curr.val) {
            curr = curr.left; // both in left subtree
        } else if (p.val > curr.val && q.val > curr.val) {
            curr = curr.right; // both in right subtree
        } else {
            return curr; // split point = LCA
        }
    }
    return null;
}

Q2: "How would you handle a tree with millions of commits that doesn't fit in memory?"

Expected answer: "If the tree is on disk, I'd use a database index (B+ tree) on commit IDs. For LCA queries, I'd:

1. Load only the path from root to branchA.
2. Load only the path from root to branchB.
3. Compare paths to find divergence point.
4. Each path load is O(\log N) disk I/O in a balanced tree.

Alternatively, store parent pointers in the database. Then:

1. Traverse from branchA to root, mark all ancestors in a HashSet.
2. Traverse from branchB to root, return first ancestor found in the set. This requires two index lookups but works for very deep trees."

---

12. Quick Reference: Tree Idioms in Java

// ── TREE NODE ─────────────────────────────────────────────────────────────
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// ── NULL SAFETY ───────────────────────────────────────────────────────────
// ALWAYS null-check before accessing .left or .right
if (root == null) return /* base case */;

// ── QUEUE SETUP FOR BFS ───────────────────────────────────────────────────
Queue<TreeNode> queue = new ArrayDeque<>();  // preferred over LinkedList
queue.offer(root);  // add
TreeNode node = queue.poll();  // remove

// ── LEVEL SIZE TRICK ──────────────────────────────────────────────────────
while (!queue.isEmpty()) {
    int levelSize = queue.size(); // lock in current level
    for (int i = 0; i < levelSize; i++) {
        TreeNode curr = queue.poll();
        // process curr
        if (curr.left != null) queue.offer(curr.left);
        if (curr.right != null) queue.offer(curr.right);
    }
}

// ── LEAF NODE CHECK ───────────────────────────────────────────────────────
if (node.left == null && node.right == null) {
    // node is a leaf
}

// ── RECURSIVE TEMPLATE ────────────────────────────────────────────────────
int solve(TreeNode node) {
    if (node == null) return /* base */;
    int left = solve(node.left);
    int right = solve(node.right);
    return /* combine(left, right) */;
}

// ── GLOBAL VARIABLE FOR TRACKING ──────────────────────────────────────────
class Solution {
    private int maxDiameter = 0;  // track across all recursion
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return maxDiameter;
    }
    private int height(TreeNode node) {
        // update maxDiameter in post-order
    }
}

// ── BST ITERATIVE SEARCH (NO RECURSION) ───────────────────────────────────
TreeNode curr = root;
while (curr != null) {
    if (target == curr.val) return curr;
    else if (target < curr.val) curr = curr.left;
    else curr = curr.right;
}

// ── BUILDING A TREE FROM ARRAY (for testing) ─────────────────────────────
// Use level-order with null markers
TreeNode buildTree(Integer[] arr) {
    if (arr == null || arr.length == 0) return null;
    TreeNode root = new TreeNode(arr[0]);
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    int i = 1;
    while (i < arr.length) {
        TreeNode curr = queue.poll();
        if (arr[i] != null) {
            curr.left = new TreeNode(arr[i]);
            queue.offer(curr.left);
        }
        i++;
        if (i < arr.length && arr[i] != null) {
            curr.right = new TreeNode(arr[i]);
            queue.offer(curr.right);
        }
        i++;
    }
    return root;
}