Binary Trees

Why this module exists

Binary trees are fundamental to computer science. They appear in databases (B-trees), compilers (syntax trees), file systems, and countless interview questions. Understanding tree recursion unlocks a whole category of problems.

This module covers:

1. Tree traversal and recursion patterns
2. Computing tree properties (depth, height)
3. Tree transformations (invert)
4. BST validation and properties
5. Finding ancestors (LCA)

---

1) Binary Tree Basics

A binary tree node has a value and pointers to left and right children:

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Terminology:

• Root: The top node (no parent)
• Leaf: A node with no children
• Depth: Distance from root (root has depth 0)
• Height: Distance to deepest descendant (leaf has height 0)

---

2) Tree Recursion Pattern

Most tree problems follow this pattern:

func solve(root *TreeNode) Result {
    // Base case: empty tree
    if root == nil {
        return baseValue
    }

    // Recursive case: process children
    leftResult := solve(root.Left)
    rightResult := solve(root.Right)

    // Combine results with current node
    return combine(root.Val, leftResult, rightResult)
}

The key insight: think about one node at a time. What information do you need from the children? What do you return to the parent?

---

3) Tree Traversals

Three classic orderings, all O(n):

Inorder (Left, Root, Right) — gives sorted order for BST:

func inorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }
    inorder(root.Left, result)
    *result = append(*result, root.Val)
    inorder(root.Right, result)
}

Preorder (Root, Left, Right) — useful for copying trees:

func preorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }
    *result = append(*result, root.Val)
    preorder(root.Left, result)
    preorder(root.Right, result)
}

Postorder (Left, Right, Root) — useful for deletion:

func postorder(root *TreeNode, result *[]int) {
    if root == nil {
        return
    }
    postorder(root.Left, result)
    postorder(root.Right, result)
    *result = append(*result, root.Val)
}

---

4) Maximum Depth

The depth of a tree is 1 + max depth of children:

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    return 1 + max(left, right)
}

Think recursively: "My depth is 1 plus the deeper of my two subtrees."

---

5) Inverting a Tree

Swap left and right children at every node:

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // Swap children
    root.Left, root.Right = root.Right, root.Left
    // Recursively invert subtrees
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

Can also be done with a stack or queue (level-order).

---

6) Binary Search Trees (BST)

A BST has the property: for every node, all values in left subtree < node < all values in right subtree.

      5
     / \
    3   7
   / \ / \
  1  4 6  9

Key operations:

• Search: O(log n) average, O(n) worst
• Insert: O(log n) average
• Inorder traversal gives sorted sequence

---

7) Validating a BST

The naive approach (check left.val < root.val < right.val) is wrong — it only checks immediate children.

Correct approach: pass valid range down:

func isValidBST(root *TreeNode) bool {
    return validate(root, nil, nil)
}

func validate(node *TreeNode, min, max *int) bool {
    if node == nil {
        return true
    }
    if min != nil && node.Val <= *min {
        return false
    }
    if max != nil && node.Val >= *max {
        return false
    }
    return validate(node.Left, min, &node.Val) &&
           validate(node.Right, &node.Val, max)
}

Alternative: inorder traversal should produce strictly increasing sequence.

---

8) Lowest Common Ancestor (LCA)

The LCA of two nodes p and q is the deepest node that is an ancestor of both.

      3
     / \
    5   1
   / \ / \
  6  2 0  8

LCA(5, 1) = 3
LCA(5, 6) = 5 (a node can be its own ancestor)
LCA(6, 2) = 5

Algorithm:

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil {
        return root  // p and q are in different subtrees
    }
    if left != nil {
        return left
    }
    return right
}

Logic:

• If current node is p or q, return it
• Recursively search left and right subtrees
• If both return non-nil, current node is LCA
• Otherwise, return the non-nil result

---

9) Level Order Traversal (BFS)

Process nodes level by level using a queue:

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        level := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, level)
    }

    return result
}

---

10) Common Mistakes

• Forgetting nil check: Always handle root == nil first
• Wrong BST validation: Must track valid range, not just check immediate children
• Confusing depth vs height: Depth is from root, height is to leaves
• Modifying tree accidentally: Be careful with pointer reassignments
• Off-by-one in depth: Is root depth 0 or 1? Check problem statement

---

11) Complexity Analysis

Operation	Time	Space
Any traversal	O(n)	O(h) stack
Max depth	O(n)	O(h)
Invert tree	O(n)	O(h)
Validate BST	O(n)	O(h)
LCA	O(n)	O(h)
Level order	O(n)	O(w) width

Where h = height of tree (log n for balanced, n for skewed).

---

Outcomes

After this module, you should be able to:

• Implement tree traversals (inorder, preorder, postorder, level-order)
• Apply the tree recursion pattern to solve problems
• Compute tree properties like depth and height
• Validate BST property with range tracking
• Find lowest common ancestor of two nodes

---

Practice Set

1. Maximum Depth of Binary Tree (Easy) — Basic tree recursion
2. Invert Binary Tree (Easy) — Tree transformation
3. Validate Binary Search Tree (Medium) — Range tracking
4. Lowest Common Ancestor (Medium) — Subtle recursion logic

Start with Maximum Depth to understand basic recursion, then Invert to see transformation. Validate BST introduces the range-passing pattern, and LCA has a subtle logic worth mastering.