Binary Trees: Where Recursive Thinking Begins

Chapter 10: Binary Trees — Where Recursive Thinking Begins

Almost every tree interview problem can be summarized in one sentence: break the big problem into smaller problems on the left and right subtrees, then combine the results. That's recursion, and binary trees are the best playground for practicing recursive thinking.

If you can fluently write all four traversals (preorder, inorder, postorder, level-order) in both recursive and iterative forms, and solve classic problems like lowest common ancestor, serialization, and path sum — you've mastered the core of recursive thinking. Backtracking, divide-and-conquer, and dynamic programming in later chapters are all variations of this "split → recurse → merge" pattern.

Level 1 · What You Need to Know

10.1 Basic Concepts

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

Key properties:

• A binary tree with n nodes has n-1 edges
• A tree of height h has at most 2^(h+1) - 1 nodes
• A complete binary tree has height O(log n)

10.2 Four Traversals

Binary trees have four traversal orders. The first three are depth-first (DFS), the last is breadth-first (BFS):

# Preorder: root → left → right
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# Inorder: left → root → right
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Postorder: left → right → root
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# Level-order (BFS)
from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Memory aid: Pre/in/post refers to when the root is visited. Preorder = root first, inorder = root in the middle, postorder = root last. Left subtree always comes before right.

Example for this tree:

        1
       / \
      2   3
     / \
    4   5

10.3 The Recursion Template

Nearly all binary tree recursion problems follow this template:

def solve(root):
    # 1. Base case
    if not root:
        return base_value

    # 2. Recurse on left and right subtrees
    left_result = solve(root.left)
    right_result = solve(root.right)

    # 3. Combine results
    return combine(root.val, left_result, right_result)

Example: Maximum depth

def max_depth(root):
    if not root:
        return 0
    left = max_depth(root.left)
    right = max_depth(root.right)
    return max(left, right) + 1

Example: Check if symmetric

def is_symmetric(root):
    def check(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                check(left.left, right.right) and
                check(left.right, right.left))
    return check(root.left, root.right) if root else True

10.4 Iterative Traversals

Recursion implicitly uses the system call stack. We can use an explicit stack to write iterative versions:

# Preorder (iterative)
def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

# Inorder (iterative) — most frequently tested
def inorder_iterative(root):
    result = []
    stack = []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

# Postorder (iterative) — reverse-preorder trick
def postorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

In interviews: If asked to "implement inorder traversal without recursion," the inorder_iterative above is the standard answer. The key insight: use a stack to simulate "go left as far as possible, process current node, then move right."

10.5 Common Mistakes

Mistake 1: Forgetting to handle None

# Wrong: crashes when root is None
def bad_depth(root):
    return max(bad_depth(root.left), bad_depth(root.right)) + 1

# Correct: check None first
def good_depth(root):
    if not root:
        return 0
    return max(good_depth(root.left), good_depth(root.right)) + 1

Mistake 2: Confusing "depth" and "height"

• Depth: from root to node, top-down
• Height: from node to farthest leaf, bottom-up
• Root's depth = 0, root's height = tree's height

Mistake 3: Creating lists in recursion

# Slow: creates new lists each call, O(n²) total
def preorder_slow(root):
    if not root:
        return []
    return [root.val] + preorder_slow(root.left) + preorder_slow(root.right)

# Fast: collect into shared list, O(n)
def preorder_fast(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return result

Level 2 · How It Works

10.6 Morris Traversal: O(1) Space

Both recursive and iterative traversals need O(h) extra space (h is tree height, worst case O(n)). Morris traversal (J. H. Morris, 1979) uses leaf nodes' null pointers to achieve O(1) space.

Core idea: temporarily use leaf nodes' right pointers as "threads" pointing back to their inorder successor, then restore after traversal.

def morris_inorder(root):
    result = []
    curr = root
    while curr:
        if not curr.left:
            result.append(curr.val)
            curr = curr.right
        else:
            # Find the rightmost node in left subtree (inorder predecessor)
            pred = curr.left
            while pred.right and pred.right != curr:
                pred = pred.right

            if not pred.right:
                # First visit: create thread
                pred.right = curr
                curr = curr.left
            else:
                # Second visit: remove thread, visit current
                pred.right = None
                result.append(curr.val)
                curr = curr.right
    return result

How it works (inorder):

1. If current node has no left child, visit it, move right
2. If it has a left child, find the rightmost node in the left subtree (inorder predecessor)
3. If predecessor's right pointer is null, create thread (point to current), move left
4. If predecessor's right pointer already points to current (second visit), remove thread, visit current, move right

Complexity: Time O(n) (each node visited at most 3 times), Space O(1).

Drawback: Temporarily modifies tree structure — unsuitable for read-only or concurrent scenarios.

10.7 Rebuilding a Binary Tree from Traversals

Classic problem: Given preorder and inorder traversal results, reconstruct the tree.

def build_tree(preorder, inorder):
    if not preorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    mid = inorder.index(root_val)
    root.left = build_tree(preorder[1:mid+1], inorder[:mid])
    root.right = build_tree(preorder[mid+1:], inorder[mid+1:])
    return root

Optimization: inorder.index() is O(n) each time, giving O(n²) total. Use a hash map for O(n):

def build_tree_optimized(preorder, inorder):
    idx_map = {val: i for i, val in enumerate(inorder)}
    pre_iter = iter(preorder)

    def helper(lo, hi):
        if lo > hi:
            return None
        root_val = next(pre_iter)
        root = TreeNode(root_val)
        mid = idx_map[root_val]
        root.left = helper(lo, mid - 1)
        root.right = helper(mid + 1, hi)
        return root

    return helper(0, len(inorder) - 1)

Which combinations uniquely determine a binary tree?

10.8 Serialization and Deserialization

Converting a binary tree to a string (serialization) and back (deserialization). Common in network transmission and persistent storage.

class Codec:
    def serialize(self, root):
        """Preorder traversal, '#' for null nodes"""
        vals = []
        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        vals = iter(data.split(','))
        def dfs():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

codec = Codec()
s = codec.serialize(root)       # "1,2,4,#,#,5,#,#,3,#,#"
new_root = codec.deserialize(s)  # Reconstructs the exact same tree

Why record null nodes? Without null markers, a preorder sequence alone cannot uniquely determine a tree (you'd need inorder too). With null markers, preorder alone suffices.

10.9 Lowest Common Ancestor (LCA)

Given two nodes p and q in a binary tree, find their lowest common ancestor.

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left if left else right

Time O(n), Space O(h). The elegance of this solution: recursion naturally handles all cases with no special-case logic.

Follow-up: For a BST, LCA can exploit the ordering property:

def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

Level 3 · What the Spec Says

10.10 Mathematical Properties

Catalan Numbers: The number of structurally distinct binary trees with n nodes is C(n) = C(2n, n) / (n+1). This sequence is called Catalan numbers (Eugene Charles Catalan, 1838).

First terms: 1, 1, 2, 5, 14, 42, 132, 429, ...

Recurrence: C(n) = sum of C(i) * C(n-1-i) for i from 0 to n-1. Meaning: left subtree has i nodes, right subtree has n-1-i nodes.

Catalan numbers also count: valid parenthesis sequences, stack-sortable permutations, triangulations of convex polygons. These problems are structurally isomorphic.

10.11 Threaded Binary Trees

Morris traversal originates from threaded binary trees, first proposed by A.J. Perlis and C. Thornton in 1960.

In a binary tree with n nodes, there are n+1 null pointers (proof: n nodes have 2n pointer fields, n-1 are used by edges, leaving n+1 null). Threaded binary trees repurpose these null pointers to store traversal information:

• If a node's left pointer is null, point it to its inorder predecessor
• If a node's right pointer is null, point it to its inorder successor

This enables O(1) space traversal. Joseph Morris gave the practical algorithm in his 1979 paper Traversing Binary Trees Simply and Cheaply.

10.12 Expression Trees and Compilers

Binary trees represent expressions in compilers. Internal nodes are operators, leaves are operands:

        +
       / \
      *   3
     / \
    2   5

Represents (2 * 5) + 3.

• Preorder gives prefix notation (Polish notation): + * 2 5 3
• Inorder gives infix notation: 2 * 5 + 3 (needs parentheses for disambiguation)
• Postorder gives postfix notation (Reverse Polish Notation): 2 5 * 3 +

Compilers parse source code into an Abstract Syntax Tree (AST), which is a generalization of expression trees. Python's ast module lets you inspect ASTs:

import ast
tree = ast.parse("x = 2 * 5 + 3")
print(ast.dump(tree, indent=2))

Level 4 · Edge Cases and Pitfalls

10.13 Recursion Depth and Stack Overflow

Python's default recursion limit is 1000. For degenerate trees (chain-shaped), more than 1000 nodes causes stack overflow:

# Build a degenerate right-chain tree
root = TreeNode(0)
curr = root
for i in range(1, 1500):
    curr.right = TreeNode(i)
    curr = curr.right

inorder(root)  # RecursionError: maximum recursion depth exceeded

Solutions:

1. Use iterative traversal (explicit stack)
2. sys.setrecursionlimit(10000) — temporary fix, not recommended
3. Morris traversal (O(1) space)

In interviews: If the interviewer says "input can be very large," prefer iterative solutions.

10.14 Binary Trees vs. N-ary Trees

Interviews occasionally feature N-ary trees (each node has arbitrary number of children):

class NaryNode:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children or []

def nary_preorder(root):
    if not root:
        return []
    result = [root.val]
    for child in root.children:
        result.extend(nary_preorder(child))
    return result

def nary_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            queue.extend(node.children)
        result.append(level)
    return result

Conversion: Any N-ary tree can be converted to a binary tree (left-child right-sibling representation), which is the foundation for BSTs in Chapter 11.

10.15 Interview Problems

Problem 1: Invert Binary Tree (LeetCode #226)

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

This problem has a famous story: Homebrew creator Max Howell was rejected by Google for not solving it. His tweet about it sparked a major debate about whether interview processes are reasonable.

Problem 2: Validate BST (LeetCode #98)

def is_valid_bst(root):
    def check(node, lo, hi):
        if not node:
            return True
        if node.val <= lo or node.val >= hi:
            return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)
    return check(root, float('-inf'), float('inf'))

Common mistake: Checking only node.left.val < node.val < node.right.val is insufficient. BST requires all nodes in the left subtree to be less than root, not just the immediate left child.

Problem 3: Diameter of Binary Tree (LeetCode #543)

def diameter_of_binary_tree(root):
    max_d = 0
    def depth(node):
        nonlocal max_d
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        max_d = max(max_d, left + right)
        return max(left, right) + 1
    depth(root)
    return max_d

Problem 4: Path Sum III (LeetCode #437)

from collections import defaultdict

def path_sum(root, target_sum):
    count = 0
    prefix = defaultdict(int)
    prefix[0] = 1

    def dfs(node, curr_sum):
        nonlocal count
        if not node:
            return
        curr_sum += node.val
        count += prefix[curr_sum - target_sum]
        prefix[curr_sum] += 1
        dfs(node.left, curr_sum)
        dfs(node.right, curr_sum)
        prefix[curr_sum] -= 1  # backtrack

    dfs(root, 0)
    return count

This elegantly combines prefix sums (Chapter 3) and hash tables (Chapter 8). If the path sum from root to current node is curr_sum, and some ancestor had prefix sum curr_sum - target, then the path between them sums to target.

10.16 Binary Trees in Production

Binary trees are not an isolated data structure — they're the foundation for every tree structure that follows. Master the recursive thinking and traversal techniques in this chapter, and BSTs, heaps, tries, and segment trees are all just binary trees with added constraints.

Chapter Summary

Exercises:

1. Implement iterative postorder traversal without the "reverse preorder" trick (hint: track the last visited node).
2. Given level-order [3,9,20,null,null,15,7], draw the tree and write all three DFS traversals.
3. Can preorder + postorder alone (no inorder) uniquely determine a binary tree? Give a counterexample.
4. Implement a function to check if one binary tree is a subtree of another (LeetCode #572).

Next chapter: Chapter 11 adds an "ordering constraint" to binary trees — the Binary Search Tree. You'll see why BST lookup is O(log n), why naive BSTs can degrade to linked lists, and how red-black trees use rotations and recoloring to maintain balance.