PATTERN 9 OF 22

Trees (DFS)

Explore binary trees using depth-first search. Master recursive traversals (preorder, inorder, postorder), state passing through call stacks, bottom-up computation, and iterative DFS with an explicit stack.

Time: O(n)

Space: O(h) where h = tree height

Learn & Reference

Understanding the Pattern

Trees (DFS) Pattern

A binary tree is a hierarchical data structure where each node has at most two children: left and right. Depth-first search (DFS) explores as deep as possible along each branch before backtracking. Because trees are recursive structures — every subtree is itself a tree — recursion is the natural tool for DFS.

Core Concept

Every node has three fields: val (the data), left (pointer to the left child or null), and right (pointer to the right child or null). The tree is accessed through its root pointer.

The key insight: any property of a tree can be computed by combining the answers from its left and right subtrees. This recursive decomposition is the foundation of nearly every DFS solution.

Key Techniques

1. Recursive Preorder, Inorder, and Postorder Traversal

The three classic DFS orderings differ only in when you process the current node relative to its children:

Preorder (root, left, right): Process the node first, then recurse left, then right. Used for serialization and copying trees.
Inorder (left, root, right): Recurse left, process the node, then recurse right. On a BST, this visits nodes in sorted order.
Postorder (left, right, root): Recurse left, recurse right, then process the node. Used when you need children's results before computing the parent's (e.g., computing height).

Tree:     1
         / \
        2   3
Preorder:  [1, 2, 3]
Inorder:   [2, 1, 3]
Postorder: [2, 3, 1]

2. Base Case Design

Every recursive tree function needs a base case for null nodes. The most common pattern:

if node is null:
    return base_value  (0, True, [], -infinity, etc.)

Choosing the right base value is critical. For height, return 0 (or -1 depending on convention). For "is valid BST," return True. For path sum, return False. The base value should be the identity element for your combining operation.

3. State Passing (Top-Down)

Pass information from parent to child through function parameters. This is the top-down approach — the parent tells its children what they need to know.

Examples:

Validate BST: pass (low, high) bounds down; each node checks low < val < high
Path sum: pass the remaining target sum minus the current node's value
Depth tracking: pass the current depth as a parameter, incrementing at each level

4. Bottom-Up Computation (Postorder)

Compute answers from leaves upward. Each node receives results from both children and combines them. This is the postorder approach — children report up to their parent.

Examples:

Max depth: 1 + max(left_depth, right_depth)
Is balanced: check both subtrees are balanced AND their heights differ by at most 1
Diameter: at each node, the longest path through it is left_height + right_height

5. Iterative DFS with Explicit Stack

Replace recursion with your own stack. Push the root, then loop: pop a node, process it, push its children (right first, then left, so left is processed first).

This is useful when recursion depth might cause a stack overflow (very deep or skewed trees), or when you need fine-grained control over traversal order.

stack = [root]
while stack:
    node = stack.pop()
    process(node)
    if node.right: stack.push(node.right)
    if node.left:  stack.push(node.left)

When DFS Fails

You need level-by-level processing (e.g., "average of each level") -> use BFS (level-order traversal with a queue)
You need the shortest path in an unweighted tree/graph -> BFS finds it naturally; DFS does not
The tree is extremely wide and shallow -> BFS uses O(width) space, DFS uses O(height) which is better; but if you need level info, BFS is cleaner
You need to process nodes in level order -> use BFS

Common Mistakes

Forgetting the null base case: Every recursive function must handle node == null. Missing this causes null pointer exceptions on leaf nodes' children. Always write the base case first before any other logic
Confusing top-down vs. bottom-up: Top-down passes state via parameters (preorder). Bottom-up returns results from children (postorder). Mixing them up leads to incorrect results. Ask yourself: "Does the parent need to tell the child something, or does the child need to report to the parent?"
Mutating shared state incorrectly: When building paths or collecting results, passing a mutable list and forgetting to backtrack (remove the last element after recursing) causes paths to bleed into each other. Either copy the list at each call or explicitly backtrack
Returning the wrong value from the base case: The base case return value must be the identity for your combining operation. Returning 0 for max depth is correct, but returning 0 for min depth is wrong (it would make every tree have min depth 0). Think carefully about what null means in your problem
Stack overflow on skewed trees: A tree with n nodes can have height n (a linked list shape). Recursive DFS uses O(n) call stack space in this case. For very large trees, use iterative DFS with an explicit stack to avoid stack overflow

When to Use

Given the root of a binary tree in the problem statement

Finding the depth, height, or diameter of a tree

Path-related problems (root-to-leaf path, path sum, all paths)

Validating properties of a BST (is valid BST, is balanced, is symmetric)

Inverting or mirroring a tree

Lowest common ancestor (LCA) of two nodes

Serialization / deserialization of a binary tree

Constructing a tree from traversal arrays (preorder + inorder)

Computing subtree properties (sum, count, max, min)

Any problem where the answer for a node depends on answers from its subtrees

Keywords: binary tree, root, left, right, subtree, depth, height, traversal, preorder, inorder, postorder, BST, balanced, path, ancestor

Template

1# --- TreeNode Definition ---
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8# --- Recursive DFS Traversal Template ---
9def dfs(root):
10    if not root:
11        return  # base case
12
13    # Preorder: process here (before children)
14    print(root.val)
15
16    dfs(root.left)
17
18    # Inorder: process here (between children)
19
20    dfs(root.right)
21
22    # Postorder: process here (after children)
23
24# --- Iterative DFS with Explicit Stack ---
25def dfs_iterative(root):
26    if not root:
27        return []
28    result = []
29    stack = [root]
30    while stack:
31        node = stack.pop()
32        result.append(node.val)
33        # Push right first so left is processed first
34        if node.right:
35            stack.append(node.right)
36        if node.left:
37            stack.append(node.left)
38    return result

{ }

Syntax Reference

1# --- Python: TreeNode Definition ---
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8# --- Null Check (base case) ---
9if not root:
10    return  # base value
11
12# --- Access Children ---
13root.left   # left child (TreeNode or None)
14root.right  # right child (TreeNode or None)
15root.val    # node value
16
17# --- Recursive DFS Skeleton ---
18def dfs(node):
19    if not node:
20        return base_value
21    left_result = dfs(node.left)
22    right_result = dfs(node.right)
23    return combine(node.val, left_result, right_result)
24
25# --- Create a Tree Node ---
26node = TreeNode(5)
27node.left = TreeNode(3)
28node.right = TreeNode(7)

📋

Common Recipes

1# --- Inorder Traversal (Iterative with Stack) ---
2def inorder_traversal(root):
3    result = []
4    stack = []
5    curr = root
6    while curr or stack:
7        while curr:
8            stack.append(curr)
9            curr = curr.left
10        curr = stack.pop()
11        result.append(curr.val)
12        curr = curr.right
13    return result
14
15# --- Max Depth (Recursive) ---
16def max_depth(root):
17    if not root:
18        return 0
19    return 1 + max(max_depth(root.left), max_depth(root.right))
20
21# --- Invert Tree (Recursive) ---
22def invert_tree(root):
23    if not root:
24        return None
25    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
26    return root
27
28# --- Validate BST (with Bounds) ---
29def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
30    if not root:
31        return True
32    if root.val <= lo or root.val >= hi:
33        return False
34    return (is_valid_bst(root.left, lo, root.val) and
35            is_valid_bst(root.right, root.val, hi))

O(n)

Complexity

Operation	Time	Space
DFS traversal (any order)	O(n)	O(h)
Find a node	O(n)	O(h)
Invert tree	O(n)	O(h)
Validate BST	O(n)	O(h)
Serialize / deserialize	O(n)	O(n)
Balanced tree: h = log n	-	O(log n)
Skewed tree: h = n	-	O(n)

Watch Out

✗You need level-by-level processing (e.g., "average of each level") -> use BFS (level-order traversal with a queue)
✗You need the shortest path in an unweighted tree/graph -> BFS finds it naturally; DFS does not
✗The tree is extremely wide and shallow -> BFS uses O(width) space, DFS uses O(height) which is better; but if you need level info, BFS is cleaner
✗You need to process nodes in level order -> use BFS
✗Forgetting the null base case: Every recursive function must handle `node == null`. Missing this causes null pointer exceptions on leaf nodes' children. Always write the base case first before any other logic
✗Confusing top-down vs. bottom-up: Top-down passes state via parameters (preorder). Bottom-up returns results from children (postorder). Mixing them up leads to incorrect results. Ask yourself: "Does the parent need to tell the child something, or does the child need to report to the parent?"
✗Mutating shared state incorrectly: When building paths or collecting results, passing a mutable list and forgetting to backtrack (remove the last element after recursing) causes paths to bleed into each other. Either copy the list at each call or explicitly backtrack
✗Returning the wrong value from the base case: The base case return value must be the identity for your combining operation. Returning 0 for max depth is correct, but returning 0 for min depth is wrong (it would make every tree have min depth 0). Think carefully about what null means in your problem
✗Stack overflow on skewed trees: A tree with n nodes can have height n (a linked list shape). Recursive DFS uses O(n) call stack space in this case. For very large trees, use iterative DFS with an explicit stack to avoid stack overflow

PRACTICE PROBLEMS

Matrix / 2D Arrays

Trees (BFS)