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

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.