Binary Tree Interview Patterns: Complete Guide

Binary trees are the single most tested topic in coding interviews. They appear in every company, at every level, in some form. The good news: there are a finite number of patterns, and once you recognize them, even “hard” problems become combinations of patterns you already know.

This guide distills everything into actionable patterns, decision frameworks, and template code you can apply immediately.

---

The 20 Patterns That Cover 90% of Tree Problems

Pattern 1: Height / Depth Calculation

When: Any problem asking for height, depth, or balanced-ness.

def height(root):
    """Return height of tree (-1 for empty, 0 for leaf)."""
    if not root:
        return -1
    return 1 + max(height(root.left), height(root.right))

Used in: Maximum Depth (104), Balanced Binary Tree (110), Minimum Depth (111).

---

Pattern 2: Path Sum (Root to Leaf)

When: Check if a root-to-leaf path sums to a target.

def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == target
    return (has_path_sum(root.left, target - root.val) or
            has_path_sum(root.right, target - root.val))

Used in: Path Sum (112), Path Sum II (113), Path Sum III (437).

---

Pattern 3: Diameter / Longest Path

When: Find the longest path between any two nodes.

def diameter(root):
    result = [0]

    def dfs(node):
        if not node:
            return -1
        left = dfs(node.left)
        right = dfs(node.right)
        result[0] = max(result[0], left + right + 2)
        return 1 + max(left, right)

    dfs(root)
    return result[0]

Key insight: The diameter passes through some node where left_height + right_height + 2 is maximized. Compute this at every node while returning height upward.

---

Pattern 4: LCA (Lowest Common Ancestor)

When: Find the deepest node that is an ancestor of both p and q.

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

Used in: LCA of Binary Tree (236), LCA of BST (235), Distance Between Nodes.

---

Pattern 5: Serialize / Deserialize

When: Convert tree to string and back.

def serialize(root):
    if not root:
        return "null"
    return f"{root.val},{serialize(root.left)},{serialize(root.right)}"

def deserialize(data):
    vals = iter(data.split(","))

    def build():
        val = next(vals)
        if val == "null":
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node

    return build()

---

Pattern 6: Level-Order Traversal (BFS)

The BFS template that solves 10+ problems:

from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            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

---

Pattern 7: Zigzag Level Order

Variation of Pattern 6 — alternate direction each level.

def zigzag_level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])
    left_to_right = True

    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)

        if not left_to_right:
            level.reverse()

        result.append(level)
        left_to_right = not left_to_right

    return result

---

Pattern 8: Right Side View

When: Return what you see looking at the tree from the right.

def right_side_view(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                result.append(node.val)  # Last node in level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return result

---

Pattern 9: Validate BST

When: Check if a tree is a valid BST.

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

Common mistake: Using root.left.val {'<'} root.val only checks immediate children, not all descendants.

---

Pattern 10: Build Tree from Traversals

When: Construct a tree from preorder + inorder, or postorder + inorder.

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None

    root = TreeNode(preorder[0])
    mid = inorder.index(preorder[0])

    root.left = build_tree(preorder[1:mid + 1], inorder[:mid])
    root.right = build_tree(preorder[mid + 1:], inorder[mid + 1:])

    return root

Optimization: Use a hash map for the inorder index lookup to go from O(n^2) to O(n).

---

Pattern 11: Mirror / Symmetric Tree

def is_symmetric(root):
    def mirror(t1, t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return (t1.val == t2.val and
                mirror(t1.left, t2.right) and
                mirror(t1.right, t2.left))

    return mirror(root, root)

---

Pattern 12: Invert Binary Tree

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

---

Pattern 13: Subtree Check

def is_subtree(root, sub):
    if not root:
        return False
    if same_tree(root, sub):
        return True
    return is_subtree(root.left, sub) or is_subtree(root.right, sub)

def same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val and
            same_tree(p.left, q.left) and
            same_tree(p.right, q.right))

---

Pattern 14: Maximum Path Sum

def max_path_sum(root):
    result = [float('-inf')]

    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)   # Ignore negative paths
        right = max(dfs(node.right), 0)
        result[0] = max(result[0], left + right + node.val)
        return node.val + max(left, right)

    dfs(root)
    return result[0]

---

Pattern 15: Vertical Order Traversal

from collections import defaultdict, deque

def vertical_order(root):
    if not root:
        return []

    col_map = defaultdict(list)
    queue = deque([(root, 0)])  # (node, column)
    min_col = max_col = 0

    while queue:
        node, col = queue.popleft()
        col_map[col].append(node.val)
        min_col = min(min_col, col)
        max_col = max(max_col, col)

        if node.left:
            queue.append((node.left, col - 1))
        if node.right:
            queue.append((node.right, col + 1))

    return [col_map[c] for c in range(min_col, max_col + 1)]

---

Pattern 16: Flatten Tree (Preorder Threading)

def flatten(root):
    current = root
    while current:
        if current.left:
            runner = current.left
            while runner.right:
                runner = runner.right
            runner.right = current.right
            current.right = current.left
            current.left = None
        current = current.right

---

Pattern 17: Tree Pruning (Post-order)

def prune(root, condition):
    if not root:
        return None
    root.left = prune(root.left, condition)
    root.right = prune(root.right, condition)
    if condition(root) and not root.left and not root.right:
        return None
    return root

---

Pattern 18: Parent Pointer + BFS (Distance K)

def distance_k(root, target, k):
    parent = {}

    def build(node, par=None):
        if node:
            parent[node] = par
            build(node.left, node)
            build(node.right, node)

    build(root)

    queue = deque([(target, 0)])
    visited = {target}
    result = []

    while queue:
        node, dist = queue.popleft()
        if dist == k:
            result.append(node.val)
            continue
        for neighbor in [node.left, node.right, parent[node]]:
            if neighbor and neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return result

---

Pattern 19: BST Iterator (Controlled In-order)

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        if node.right:
            self._push_left(node.right)
        return node.val

    def hasNext(self):
        return bool(self.stack)

---

Pattern 20: Morris Traversal (O(1) Space)

def morris_inorder(root):
    result = []
    current = root

    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            # Find inorder predecessor
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right

            if not pred.right:
                # Create thread
                pred.right = current
                current = current.left
            else:
                # Remove thread
                pred.right = None
                result.append(current.val)
                current = current.right

    return result

---

DFS vs BFS: When to Use Which

Use DFS when…	Use BFS when…
You need to process all root-to-leaf paths	You need level-by-level information
The answer involves height or depth	You need the shortest path (unweighted)
You’re building the tree (preorder/postorder)	You need right/left side view
You need post-order processing (pruning, diameter)	You need zigzag or vertical traversal
Space is a concern and tree is balanced (O(log n))	Tree is skewed (BFS uses O(width) < O(height))

Rule of thumb: If the problem mentions “level”, “width”, “shortest”, or “view” — use BFS. Otherwise, DFS is usually simpler.

---

Recursive vs Iterative: Tradeoffs

Recursive	Iterative
Cleaner, more intuitive code	No stack overflow risk
Implicit call stack	Explicit stack — more control
Harder to pause and resume	Can stop mid-traversal (iterator)
O(h) space from call stack	O(h) space from explicit stack
Best for most interview problems	Best for iterators, Morris, and production code

Interview advice: Start recursive. Only switch to iterative if asked, or if the problem requires pausing traversal (like BST iterator).

---

Level-Order Tricks

Bottom-Left Value

def find_bottom_left(root):
    queue = deque([root])
    node = None
    while queue:
        node = queue.popleft()
        # Push RIGHT first, then LEFT
        # Last node processed will be bottom-left
        if node.right:
            queue.append(node.right)
        if node.left:
            queue.append(node.left)
    return node.val

Average of Levels

def average_of_levels(root):
    result = []
    queue = deque([root])

    while queue:
        level_sum = 0
        level_size = len(queue)

        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level_sum / level_size)

    return result

Maximum Width of Binary Tree

def width_of_binary_tree(root):
    if not root:
        return 0

    max_width = 0
    queue = deque([(root, 0)])  # (node, index)

    while queue:
        level_size = len(queue)
        _, first_index = queue[0]

        for _ in range(level_size):
            node, index = queue.popleft()
            if node.left:
                queue.append((node.left, 2 * index))
            if node.right:
                queue.append((node.right, 2 * index + 1))

        max_width = max(max_width, index - first_index + 1)

    return max_width

---

Common Mistakes That Cost Offers

Mistake 1: Confusing height and depth

Height = edges from node DOWN to deepest leaf
Depth  = edges from root DOWN to node

Height of tree = height of root = max depth of any leaf

Mistake 2: Not handling the empty tree

Always start with:

if not root:
    return ...  # base case

Mistake 3: Modifying the tree unintentionally

When the problem says “return a value”, don’t modify the tree structure. If you need to modify, check whether the problem allows it.

Mistake 4: Wrong base case for leaf nodes

# WRONG: "not root" is not the same as "root is a leaf"
if not root:
    # This is an empty subtree, NOT a leaf

# RIGHT: Check for leaf explicitly
if not root.left and not root.right:
    # This is a leaf node

Mistake 5: Forgetting BST validation requires global bounds

# WRONG: Only checks immediate children
def is_bst_wrong(root):
    if not root:
        return True
    if root.left and root.left.val >= root.val:
        return False
    if root.right and root.right.val <= root.val:
        return False
    return is_bst_wrong(root.left) and is_bst_wrong(root.right)

# This accepts invalid BSTs like:
#     5
#    / \
#   1   6
#      / \
#     3   7    ← 3 is less than 5 but in right subtree!

Mistake 6: Using result = 0 instead of result = [0] in nested functions

# WRONG in Python 3 (without nonlocal):
def dfs():
    result = 0
    def helper(node):
        result += 1  # UnboundLocalError!

# RIGHT:
def dfs():
    result = [0]
    def helper(node):
        result[0] += 1  # Works!

# ALSO RIGHT:
def dfs():
    result = 0
    def helper(node):
        nonlocal result
        result += 1

---

Complexity Cheatsheet

Operation	Time	Space	Notes
DFS traversal	O(n)	O(h)	h = log n balanced, n skewed
BFS traversal	O(n)	O(w)	w = max width, up to n/2
BST search	O(h)	O(1) iter / O(h) rec
BST insert	O(h)	O(h)
BST delete	O(h)	O(h)
Build from sorted array	O(n)	O(n)
Build from preorder + inorder	O(n)	O(n)	Use hashmap for index
LCA	O(n)	O(h)
Morris traversal	O(n)	O(1)	Modifies tree temporarily
Serialize / Deserialize	O(n)	O(n)

Where h = tree height, w = max width, n = number of nodes.

Balanced tree: h = O(log n), w = O(n/2) Skewed tree: h = O(n), w = O(1)

---

Template Code: The DFS Framework

Almost every DFS tree problem fits this template:

def solve(root):
    """Generic DFS framework for tree problems."""
    # Global result — mutable container or nonlocal
    result = [initial_value]

    def dfs(node, state):
        # Base case
        if not node:
            return base_return

        # Pre-order processing (if needed)
        # ... do something before children ...

        # Recurse
        left_result = dfs(node.left, updated_state)
        right_result = dfs(node.right, updated_state)

        # Post-order processing (if needed)
        # ... combine left_result and right_result ...

        # Update global result (if needed)
        result[0] = max(result[0], some_computation)

        # Return value to parent
        return value_for_parent

    dfs(root, initial_state)
    return result[0]

---

Template Code: The BFS Framework

from collections import deque

def solve_bfs(root):
    """Generic BFS framework for tree problems."""
    if not root:
        return default_value

    result = []
    queue = deque([root])
    level = 0

    while queue:
        level_size = len(queue)
        level_data = []

        for i in range(level_size):
            node = queue.popleft()

            # Process node
            level_data.append(node.val)

            # Add children
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        # Process level
        result.append(level_data)
        level += 1

    return result

---

Interview Strategy: 5-Step Framework

When you see a tree problem in an interview:

Step 1: Identify the pattern. Does it match one of the 20 patterns above? Most problems are variations.

Step 2: Choose DFS or BFS. Level-related problems suggest BFS. Path/height/subtree problems suggest DFS.

Step 3: Determine traversal order. Need full child info before processing? Use post-order. Building top-down? Use pre-order. BST sorted access? Use in-order.

Step 4: Decide on return value. What should each recursive call return to its parent? Height? Boolean? Tuple of values?

Step 5: Handle edge cases. Empty tree, single node, skewed tree, negative values.

---

Practice Problems by Pattern

Pattern	Problem	LeetCode #	Difficulty
Height	Maximum Depth of Binary Tree	104	Easy
Path Sum	Path Sum III	437	Medium
Diameter	Diameter of Binary Tree	543	Easy
LCA	LCA of Binary Tree	236	Medium
Serialize	Serialize and Deserialize	297	Hard
Level Order	Binary Tree Level Order	102	Medium
Zigzag	Zigzag Level Order	103	Medium
Right View	Right Side View	199	Medium
Validate BST	Validate BST	98	Medium
Build Tree	Construct from Pre + In	105	Medium
Symmetric	Symmetric Tree	101	Easy
Invert	Invert Binary Tree	226	Easy
Max Path Sum	Binary Tree Max Path Sum	124	Hard
Vertical	Vertical Order Traversal	987	Hard
Flatten	Flatten to Linked List	114	Medium
Pruning	Binary Tree Pruning	814	Medium
Distance K	All Nodes Distance K	863	Medium
Iterator	BST Iterator	173	Medium
Morris	Recover BST (no extra space)	99	Medium
Width	Maximum Width	662	Medium

---

Key Takeaways

• 20 patterns cover 90% of tree problems. Learn the patterns, not individual solutions.
• DFS for depth/path problems, BFS for level/width problems. This simple rule works almost every time.
• Post-order is for bottom-up computation (height, pruning, diameter). Pre-order is for top-down propagation (serialization, path building).
• Always handle the empty tree as your first line. Then decide if leaf nodes need special treatment.
• BST problems exploit sorted order — use lo/hi bounds for validation, iterator for controlled access, and binary search for queries.
• Practice with intent: don’t just solve problems, categorize them by pattern. After 50 tree problems, you’ll recognize patterns instantly.
• Start recursive in interviews. It’s cleaner and faster to write. Only switch to iterative if asked or if the problem demands it.