Common Tree Patterns - Learning Module

Loading content...

0/276

Maximum Depth and Width

Measuring Trees — Height, Depth, and Breadth

Every tree has two fundamental dimensional properties: how tall it grows (depth/height) and how wide it spreads (maximum width at any level). These simple measurements tell us crucial information about the tree's shape, balance, and behavior.

Depth/Height determines worst-case recursion depth, memory for algorithms, and time complexity for many operations.
Width affects level-processing algorithms, visualization requirements, and memory patterns during BFS.

While computing these seems straightforward, the problems reveal important algorithmic insights: when to use DFS vs BFS, how to think about levels, and how to handle edge cases like null nodes in width calculations. These patterns transfer directly to more complex tree problems.

What You Will Master

By the end of this page, you will:

• Implement maximum depth using both DFS (recursive) and BFS (iterative) approaches • Understand when each approach is preferable • Compute maximum width with proper handling of null positions • Recognize the distinction between 'node count width' and 'positional width' • Apply these concepts to minimum depth and balanced tree checking • Build intuition for choosing DFS vs BFS in tree problems

Maximum Depth — The Fundamental Measurement

Definition:

The maximum depth (or height) of a binary tree is the number of edges on the longest path from the root to any leaf. Some definitions count nodes instead of edges — always clarify.

Conventions:

Empty tree (null root): depth = 0 (or -1 in some conventions)
Single node tree: depth = 0 (0 edges) or 1 (1 node)

We'll use the node-counting convention (depth of single node = 1) as it's more intuitive and commonly expected.

Example:

        3           Depth = 3 (nodes: 3, 2 levels down)
       / \          Or Depth = 2 (edges)
      9  20
        /  \
       15   7

Longest path: 3 → 20 → 15 (or 3 → 20 → 7)

The Recursive Insight:

Depth of a tree rooted at node N is:

0 if N is null
1 + max(depth(N.left), depth(N.right)) otherwise

This elegant formulation captures that depth is 1 level (for the current node) plus the maximum depth of either subtree.

Why maximum?

We take the max because depth means the longest path. The tree's height is determined by its deepest leaf, not its shallowest.

Visual intuition:

Think of water filling the tree from the bottom. The depth is how many levels the water covers to reach the root — determined by the deepest basin (leaf).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Computes the maximum depth of a binary tree using DFS (recursion).
 * Depth is counted in nodes (single node = depth 1).
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion stack, where h is tree height
 *         O(log n) balanced, O(n) skewed
 */
function maxDepthDFS(root: TreeNode | null): number {
    // Base case: empty tree has depth 0
    if (root === null) {
        return 0;
    }
    
    // Recursive case: 1 (this level) + max of children's depths
    const leftDepth = maxDepthDFS(root.left);
    const rightDepth = maxDepthDFS(root.right);
    
    return 1 + Math.max(leftDepth, rightDepth);
}
 
// Even more concise one-liner
const maxDepthOneLiner = (root: TreeNode | null): number =>
    root === null ? 0 : 1 + Math.max(maxDepthOneLiner(root.left), maxDepthOneLiner(root.right));

The Simplest Tree Problem

Maximum depth is often the first tree problem new learners solve. Its simplicity is deceptive — it perfectly captures recursive thinking on trees. If you truly understand why this works, you understand tree recursion. The pattern 'base case + 1 + max of children' appears in countless tree algorithms.

Maximum Depth — BFS Approach

While DFS is elegant, BFS provides an alternative perspective: count how many levels we traverse before running out of nodes.

BFS Level-by-Level:

Start with root in queue
Process all nodes at current level
Add their children to queue
Increment depth counter
Repeat until queue is empty

The number of level iterations equals the tree's depth.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Computes maximum depth using BFS (level-order traversal).
 * Count the number of levels traversed.
 * 
 * Time: O(n) - visit each node once
 * Space: O(w) - queue size, where w is maximum width
 *         O(n/2) = O(n) for complete tree's last level
 */
function maxDepthBFS(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    
    const queue: TreeNode[] = [root];
    let depth = 0;
    
    while (queue.length > 0) {
        // Process all nodes at current level
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Add children to queue for next level
            if (node.left !== null) {
                queue.push(node.left);
            }
            if (node.right !== null) {
                queue.push(node.right);
            }
        }
        
        // Completed one level
        depth++;
    }
    
    return depth;
}

DFS vs BFS for Depth — Comparison:

Aspect	DFS (Recursive)	BFS (Iterative)
Code simplicity	Very simple (3 lines)	More setup needed
Space (balanced tree)	O(log n) stack	O(n) queue
Space (skewed tree)	O(n) stack	O(1) queue
Intuition	'Depth = 1 + max children depth'	'Count levels until done'
Stack overflow risk	Yes, for very deep trees	No

When to use which:

DFS: Default choice for most tree depth problems. Simple, efficient.
BFS: When you need level information, or when tree is extremely deep (preventing stack overflow).

In practice, DFS is almost always preferred for depth calculation due to its simplicity. BFS shines when the problem inherently requires level-by-level processing.

Stack Overflow Caution

For extremely deep trees (e.g., a linked list of millions of nodes), recursive DFS will overflow the call stack. In such cases, use iterative DFS with an explicit stack or BFS. Most interview problems have reasonable tree sizes, but production code should consider this.

Minimum Depth — A Subtle Variation

Minimum depth is the shortest path from root to any leaf. At first glance, just replace max with min. But there's a subtle trap!

The Trap:

    2          Naively: min(depth(null), depth(3)) = min(0, 1) = 0
     \         But the minimum path to a LEAF is 2 → 3 (depth 2)!
      3        Node 2 has no left child, but that doesn't mean depth 0.
       \       A leaf is a node with NO children, not a null.
        4

The node 2 isn't a leaf (it has a right child), so we can't stop there. We must reach an actual leaf.

Correct Logic:

If current node is null: return 0 (or infinity if we're not at a valid leaf)
If current node is a leaf (no children): return 1
If only left child exists: return 1 + minDepth(left)
If only right child exists: return 1 + minDepth(right)
If both exist: return 1 + min(minDepth(left), minDepth(right))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Finds the minimum depth — shortest path from root to any leaf.
 * A leaf is a node with NO children.
 * 
 * CAUTION: Don't just replace max with min! Must handle nodes
 * with only one child correctly.
 * 
 * Time: O(n) worst case (all nodes on one side)
 * Space: O(h) recursion stack
 */
function minDepth(root: TreeNode | null): number {
    // Empty tree
    if (root === null) {
        return 0;
    }
    
    // Leaf node — this is a valid endpoint
    if (root.left === null && root.right === null) {
        return 1;
    }
    
    // Only right child exists — must go right
    if (root.left === null) {
        return 1 + minDepth(root.right);
    }
    
    // Only left child exists — must go left
    if (root.right === null) {
        return 1 + minDepth(root.left);
    }
    
    // Both children exist — take the shorter path
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
 
/**
 * BFS approach — often better for minimum depth!
 * Stops as soon as we find the first leaf (closest to root).
 * 
 * Time: O(n) worst case, but often O(k) where k < n
 * Space: O(w) queue width
 */
function minDepthBFS(root: TreeNode | null): number {
    if (root === null) return 0;
    
    const queue: TreeNode[] = [root];
    let depth = 1;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Found a leaf! This is the minimum depth
            if (node.left === null && node.right === null) {
                return depth;
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        depth++;
    }
    
    return depth;  // Should never reach here for valid tree
}

BFS is Optimal for Minimum Depth!

For minimum depth, BFS is often more efficient than DFS. BFS finds the closest leaf first and stops, potentially visiting far fewer nodes. DFS must explore all paths to be sure it found the shortest. For a tall, unbalanced tree with a shallow leaf, BFS can be dramatically faster.

Maximum Width — Counting Nodes at Each Level

The width of a tree has two interpretations:

Node count width: Maximum number of nodes at any level
Positional width: Maximum horizontal span including gaps (nulls count for spacing)

Let's start with node count width — simpler and more intuitive.

Example:

        1           Level 0: 1 node  (width 1)
       / \          Level 1: 2 nodes (width 2)
      3   2         Level 2: 4 nodes (width 4)
     / \   \        Level 3: 2 nodes (width 2)
    5   3   9       
   /         \      Maximum width = 4 (level 2)
  6           7

Wait, level 2 in my diagram only shows 4 slots but let me recount... Actually:

        1           Level 0: 1 node
       / \          Level 1: 2 nodes  
      3   2         Level 2: 3 nodes (5, 3, 9)
     / \   \
    5   3   9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Finds the maximum number of nodes at any single level.
 * Uses BFS to count nodes per level.
 * 
 * Time: O(n)
 * Space: O(w) where w is maximum width
 */
function maxWidthNodeCount(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    
    const queue: TreeNode[] = [root];
    let maxWidth = 0;
    
    while (queue.length > 0) {
        const levelSize = queue.length;  // This is the width at current level
        maxWidth = Math.max(maxWidth, levelSize);
        
        // Process all nodes at this level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return maxWidth;
}
 
/**
 * DFS alternative: use a depth-to-count map
 * Less common but works for this problem
 */
function maxWidthDFS(root: TreeNode | null): number {
    const levelCounts = new Map<number, number>();
    
    function dfs(node: TreeNode | null, depth: number): void {
        if (node === null) return;
        
        levelCounts.set(depth, (levelCounts.get(depth) || 0) + 1);
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
    
    dfs(root, 0);
    
    let maxWidth = 0;
    for (const count of levelCounts.values()) {
        maxWidth = Math.max(maxWidth, count);
    }
    return maxWidth;
}

BFS is Natural for Width

Width is inherently a level-by-level concept. BFS naturally processes level by level, making the width calculation trivial (just check queue size at each level). DFS requires additional bookkeeping to track which nodes are at which level.

Maximum Width — Positional Width (Including Gaps)

Positional width is more nuanced: it's the maximum horizontal distance between the leftmost and rightmost nodes at any level, including null gaps.

Example:

           1              Level 0: positions [0], width = 1
          / \             Level 1: positions [0, 1], width = 2
         3   2            Level 2: positions [0, 3], width = 4 (gap in middle!)
        /     \           
       5       9          Width = rightmost - leftmost + 1 = 3 - 0 + 1 = 4

Even though level 2 has only 2 nodes, its positional width is 4 because positions 0, 1, 2, 3 would exist in a complete tree.

Position Indexing:

We assign positions to nodes as if the tree were complete:

Root: position 0
Left child of node at position p: position 2p + 1
Right child of node at position p: position 2p + 2

(Or using 1-indexed: root = 1, left = 2p, right = 2p + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Finds maximum positional width — horizontal span including gaps.
 * Uses BFS with position tracking.
 * 
 * Position assignment (0-indexed):
 * - Left child of node at pos p: 2*p + 1
 * - Right child of node at pos p: 2*p + 2
 * 
 * Width at a level = rightmost_pos - leftmost_pos + 1
 * 
 * Time: O(n)
 * Space: O(w) for queue
 * 
 * Note: For very deep trees, positions can overflow. Use BigInt
 * or subtract levelMinPos to keep positions small.
 */
function widthOfBinaryTree(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    
    // Queue stores [node, position]
    let queue: Array<[TreeNode, bigint]> = [[root, 0n]];
    let maxWidth = 0n;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        // Get leftmost and rightmost positions at this level
        const leftmostPos = queue[0][1];
        const rightmostPos = queue[queue.length - 1][1];
        
        // Width = span from left to right, inclusive
        const levelWidth = rightmostPos - leftmostPos + 1n;
        if (levelWidth > maxWidth) {
            maxWidth = levelWidth;
        }
        
        // Process level, build next level's queue
        const nextQueue: Array<[TreeNode, bigint]> = [];
        
        for (const [node, pos] of queue) {
            // Normalize positions to prevent overflow
            // By subtracting leftmostPos, we restart counting from 0 each level
            const normalizedPos = pos - leftmostPos;
            
            if (node.left !== null) {
                nextQueue.push([node.left, normalizedPos * 2n + 1n]);
            }
            if (node.right !== null) {
                nextQueue.push([node.right, normalizedPos * 2n + 2n]);
            }
        }
        
        queue = nextQueue;
    }
    
    return Number(maxWidth);
}

Position Overflow — A Real Danger!

In a skewed tree of depth 100, positions can reach 2^100 — far beyond integer limits! The solution is to normalize positions per level by subtracting the level's minimum position. This keeps numbers manageable while preserving relative distances. Always do this in production code.

Why Track Positions?

Positional width matters for:

Tree visualization (how much horizontal space is needed)
Serialization to array (array size = max width at any level)
Collision detection in tree layouts
Certain geometry problems on trees

Node-count width is simpler but doesn't capture the tree's 'spread'. A tree with all left children has node-count max-width of 1 but effectively spreads across the visualization.

Balanced Tree — Combining Depth Analysis

A balanced binary tree is one where the depth of the two subtrees of every node never differs by more than 1. This ensures O(log n) height, which is critical for efficient tree operations.

Definition:

For every node N: |height(N.left) - height(N.right)| ≤ 1

Why balance matters:

Balanced tree of n nodes: height = O(log n)
Unbalanced tree: height can be O(n)
Operations like search, insert, delete are O(height)
Balanced → O(log n) operations, unbalanced → O(n) operations

Checking Balance:

We need to compute heights AND verify the balance condition at every node. The pattern is similar to diameter — compute a helper value (height) while checking a condition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Determines if a binary tree is height-balanced.
 * A balanced tree has subtree heights differing by at most 1, at every node.
 * 
 * Approach: Compute height recursively, return -1 if unbalanced detected.
 * This allows early termination when imbalance is found.
 * 
 * Time: O(n) - each node visited once
 * Space: O(h) - recursion stack
 */
function isBalanced(root: TreeNode | null): boolean {
    return checkHeight(root) !== -1;
}
 
/**
 * Returns the height of the tree if balanced, or -1 if unbalanced.
 * The -1 serves as a sentinel: "don't bother, there's imbalance below"
 */
function checkHeight(node: TreeNode | null): number {
    // Base case: null has height 0
    if (node === null) {
        return 0;
    }
    
    // Get left subtree height (or -1 if left is unbalanced)
    const leftHeight = checkHeight(node.left);
    if (leftHeight === -1) {
        return -1;  // Left subtree is unbalanced, propagate failure
    }
    
    // Get right subtree height (or -1 if right is unbalanced)
    const rightHeight = checkHeight(node.right);
    if (rightHeight === -1) {
        return -1;  // Right subtree is unbalanced, propagate failure
    }
    
    // Check balance at this node
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;  // This node is unbalanced
    }
    
    // Return height for parent's calculation
    return 1 + Math.max(leftHeight, rightHeight);
}

Why -1 as Sentinel?

Using -1 (invalid height) to signal imbalance allows us to:

Short-circuit computation once imbalance is found
Avoid a separate boolean return value
Keep the recursion clean and O(n)

A naive approach might compute heights separately then compare — this would be O(n log n) for balanced trees due to recomputation.

Alternative: Tuple Return:

function checkBalanced(node: TreeNode | null): [boolean, number] {
    if (node === null) return [true, 0];
    
    const [leftBalanced, leftHeight] = checkBalanced(node.left);
    if (!leftBalanced) return [false, 0];
    
    const [rightBalanced, rightHeight] = checkBalanced(node.right);
    if (!rightBalanced) return [false, 0];
    
    const balanced = Math.abs(leftHeight - rightHeight) <= 1;
    return [balanced, 1 + Math.max(leftHeight, rightHeight)];
}

Both approaches work; the -1 sentinel is more concise.

Practical Applications

Depth and width measurements have direct practical applications across software engineering.

1. Recursion Depth Limits:

Tree height determines recursion stack depth. Languages have limits (often ~1000-10000 calls). Knowing your tree's expected depth helps you decide whether recursive solutions are safe.

2. Memory Allocation:

BFS queue size peaks at tree width. For visualization or processing large trees, knowing max width helps allocate appropriate buffers.

3. Algorithm Selection:

Shallow, wide trees: BFS might have high memory; DFS is safer
Deep, narrow trees: DFS might overflow; iterative BFS is safer
Balanced trees: Either works well

4. Database Query Optimization:

Query execution plans form trees. Plan depth indicates query complexity; balancing the tree (query rewriting) can dramatically improve performance.

5. Parallel Processing:

Tree width indicates parallelization opportunity at each level. Wide levels can be processed in parallel; narrow levels are sequential bottlenecks.

When Depth and Width Matter
Scenario	Key Metric	Why It Matters	Action
Recursive processing	Max depth	Stack overflow risk	Use iterative for deep trees
Level-order processing	Max width	Peak memory usage	Stream processing for wide trees
Tree balancing	Height balance	Operation efficiency	Rebalance if unbalanced
Visualization	Both	Layout dimensions	Allocate appropriate canvas
Serialization	Positional width	Array size for level-order	Pre-allocate array

Complete Binary Tree

A complete binary tree has depth ⌈log₂(n+1)⌉ and maximum width n/2 (at the last full level). These properties make complete trees ideal for array-based storage (heaps). Knowing these relationships helps you estimate tree dimensions from node count.

Summary and Key Takeaways

Depth and width form the dimensional foundation of tree analysis. Let's consolidate what we've learned:

Core Concepts Mastered

•Max depth (DFS): Simple recursive formula: 1 + max of children depths
•Max depth (BFS): Count levels until queue empties
•Min depth trap: Only leaves count — handle single-child nodes correctly
•Min depth optimization: BFS finds closest leaf first, often faster than DFS
•Width (node count): Use BFS, track queue size per level
•Width (positional): Assign positions; normalize per level to prevent overflow
•Balanced check: Compute height with -1 sentinel for early imbalance detection

DFS vs BFS Decision Framework

Choose DFS when: • Problem is about paths (root-to-leaf, depth-first properties) • Tree structure allows simple recursive formulation • Space is tight and tree is wide

Choose BFS when: • Problem is about levels (width, level-order properties) • Need to find 'closest' or 'shallowest' (early termination) • Tree is very deep and might overflow recursion stack

Module Complete:

This concludes Module 9: Common Tree Patterns & Problem Types. You've mastered:

Path Sum Problems — Accumulating values along tree paths
Lowest Common Ancestor — Finding where paths converge
Tree Symmetry & Comparison — Structural analysis and matching
Diameter of a Tree — Finding the longest path anywhere
Maximum Depth & Width — Measuring tree dimensions

These patterns form a toolkit that applies to the vast majority of tree problems. Internalize these patterns, and new tree problems become variations on familiar themes.

Module Complete!

Congratulations! You've completed Module 9 and built a comprehensive tree problem-solving toolkit. The patterns you've learned — path accumulation, ancestor finding, structural comparison, diameter computation, and dimensional analysis — transfer to countless variations. Practice applying these patterns to new problems, and you'll develop the intuition to recognize and solve tree problems with confidence.

Maximum Depth and Width

Measuring Trees — Height, Depth, and Breadth

Depth/Height determines worst-case recursion depth, memory for algorithms, and time complexity for many operations.
Width affects level-processing algorithms, visualization requirements, and memory patterns during BFS.

What You Will Master

By the end of this page, you will:

Maximum Depth — The Fundamental Measurement

Definition:

The maximum depth (or height) of a binary tree is the number of edges on the longest path from the root to any leaf. Some definitions count nodes instead of edges — always clarify.

Conventions:

Empty tree (null root): depth = 0 (or -1 in some conventions)
Single node tree: depth = 0 (0 edges) or 1 (1 node)

We'll use the node-counting convention (depth of single node = 1) as it's more intuitive and commonly expected.

Example:

        3           Depth = 3 (nodes: 3, 2 levels down)
       / \          Or Depth = 2 (edges)
      9  20
        /  \
       15   7

Longest path: 3 → 20 → 15 (or 3 → 20 → 7)

The Recursive Insight:

Depth of a tree rooted at node N is:

0 if N is null
1 + max(depth(N.left), depth(N.right)) otherwise

This elegant formulation captures that depth is 1 level (for the current node) plus the maximum depth of either subtree.

Why maximum?

We take the max because depth means the longest path. The tree's height is determined by its deepest leaf, not its shallowest.

Visual intuition:

Think of water filling the tree from the bottom. The depth is how many levels the water covers to reach the root — determined by the deepest basin (leaf).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Computes the maximum depth of a binary tree using DFS (recursion).
 * Depth is counted in nodes (single node = depth 1).
 * 
 * Time: O(n) - visit each node once
 * Space: O(h) - recursion stack, where h is tree height
 *         O(log n) balanced, O(n) skewed
 */
function maxDepthDFS(root: TreeNode | null): number {
    // Base case: empty tree has depth 0
    if (root === null) {
        return 0;
    }
    
    // Recursive case: 1 (this level) + max of children's depths
    const leftDepth = maxDepthDFS(root.left);
    const rightDepth = maxDepthDFS(root.right);
    
    return 1 + Math.max(leftDepth, rightDepth);
}
 
// Even more concise one-liner
const maxDepthOneLiner = (root: TreeNode | null): number =>
    root === null ? 0 : 1 + Math.max(maxDepthOneLiner(root.left), maxDepthOneLiner(root.right));

The Simplest Tree Problem

Maximum Depth — BFS Approach

While DFS is elegant, BFS provides an alternative perspective: count how many levels we traverse before running out of nodes.

BFS Level-by-Level:

Start with root in queue
Process all nodes at current level
Add their children to queue
Increment depth counter
Repeat until queue is empty

The number of level iterations equals the tree's depth.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Computes maximum depth using BFS (level-order traversal).
 * Count the number of levels traversed.
 * 
 * Time: O(n) - visit each node once
 * Space: O(w) - queue size, where w is maximum width
 *         O(n/2) = O(n) for complete tree's last level
 */
function maxDepthBFS(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    
    const queue: TreeNode[] = [root];
    let depth = 0;
    
    while (queue.length > 0) {
        // Process all nodes at current level
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Add children to queue for next level
            if (node.left !== null) {
                queue.push(node.left);
            }
            if (node.right !== null) {
                queue.push(node.right);
            }
        }
        
        // Completed one level
        depth++;
    }
    
    return depth;
}

DFS vs BFS for Depth — Comparison:

Aspect	DFS (Recursive)	BFS (Iterative)
Code simplicity	Very simple (3 lines)	More setup needed
Space (balanced tree)	O(log n) stack	O(n) queue
Space (skewed tree)	O(n) stack	O(1) queue
Intuition	'Depth = 1 + max children depth'	'Count levels until done'
Stack overflow risk	Yes, for very deep trees	No

When to use which:

DFS: Default choice for most tree depth problems. Simple, efficient.
BFS: When you need level information, or when tree is extremely deep (preventing stack overflow).

In practice, DFS is almost always preferred for depth calculation due to its simplicity. BFS shines when the problem inherently requires level-by-level processing.

Stack Overflow Caution

Minimum Depth — A Subtle Variation

Minimum depth is the shortest path from root to any leaf. At first glance, just replace max with min. But there's a subtle trap!

The Trap:

    2          Naively: min(depth(null), depth(3)) = min(0, 1) = 0
     \         But the minimum path to a LEAF is 2 → 3 (depth 2)!
      3        Node 2 has no left child, but that doesn't mean depth 0.
       \       A leaf is a node with NO children, not a null.
        4

The node 2 isn't a leaf (it has a right child), so we can't stop there. We must reach an actual leaf.

Correct Logic:

If current node is null: return 0 (or infinity if we're not at a valid leaf)
If current node is a leaf (no children): return 1
If only left child exists: return 1 + minDepth(left)
If only right child exists: return 1 + minDepth(right)
If both exist: return 1 + min(minDepth(left), minDepth(right))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * Finds the minimum depth — shortest path from root to any leaf.
 * A leaf is a node with NO children.
 * 
 * CAUTION: Don't just replace max with min! Must handle nodes
 * with only one child correctly.
 * 
 * Time: O(n) worst case (all nodes on one side)
 * Space: O(h) recursion stack
 */
function minDepth(root: TreeNode | null): number {
    // Empty tree
    if (root === null) {
        return 0;
    }
    
    // Leaf node — this is a valid endpoint
    if (root.left === null && root.right === null) {
        return 1;
    }
    
    // Only right child exists — must go right
    if (root.left === null) {
        return 1 + minDepth(root.right);
    }
    
    // Only left child exists — must go left
    if (root.right === null) {
        return 1 + minDepth(root.left);
    }
    
    // Both children exist — take the shorter path
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
 
/**
 * BFS approach — often better for minimum depth!
 * Stops as soon as we find the first leaf (closest to root).
 * 
 * Time: O(n) worst case, but often O(k) where k < n
 * Space: O(w) queue width
 */
function minDepthBFS(root: TreeNode | null): number {
    if (root === null) return 0;
    
    const queue: TreeNode[] = [root];
    let depth = 1;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Found a leaf! This is the minimum depth
            if (node.left === null && node.right === null) {
                return depth;
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        depth++;
    }
    
    return depth;  // Should never reach here for valid tree
}

BFS is Optimal for Minimum Depth!

Maximum Width — Counting Nodes at Each Level

The width of a tree has two interpretations:

Node count width: Maximum number of nodes at any level
Positional width: Maximum horizontal span including gaps (nulls count for spacing)

Let's start with node count width — simpler and more intuitive.

Example:

        1           Level 0: 1 node  (width 1)
       / \          Level 1: 2 nodes (width 2)
      3   2         Level 2: 4 nodes (width 4)
     / \   \        Level 3: 2 nodes (width 2)
    5   3   9       
   /         \      Maximum width = 4 (level 2)
  6           7

Wait, level 2 in my diagram only shows 4 slots but let me recount... Actually:

        1           Level 0: 1 node
       / \          Level 1: 2 nodes  
      3   2         Level 2: 3 nodes (5, 3, 9)
     / \   \
    5   3   9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Finds the maximum number of nodes at any single level.
 * Uses BFS to count nodes per level.
 * 
 * Time: O(n)
 * Space: O(w) where w is maximum width
 */
function maxWidthNodeCount(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    
    const queue: TreeNode[] = [root];
    let maxWidth = 0;
    
    while (queue.length > 0) {
        const levelSize = queue.length;  // This is the width at current level
        maxWidth = Math.max(maxWidth, levelSize);
        
        // Process all nodes at this level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return maxWidth;
}
 
/**
 * DFS alternative: use a depth-to-count map
 * Less common but works for this problem
 */
function maxWidthDFS(root: TreeNode | null): number {
    const levelCounts = new Map<number, number>();
    
    function dfs(node: TreeNode | null, depth: number): void {
        if (node === null) return;
        
        levelCounts.set(depth, (levelCounts.get(depth) || 0) + 1);
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
    
    dfs(root, 0);
    
    let maxWidth = 0;
    for (const count of levelCounts.values()) {
        maxWidth = Math.max(maxWidth, count);
    }
    return maxWidth;
}

BFS is Natural for Width

Maximum Width — Positional Width (Including Gaps)

Positional width is more nuanced: it's the maximum horizontal distance between the leftmost and rightmost nodes at any level, including null gaps.

Example:

           1              Level 0: positions [0], width = 1
          / \             Level 1: positions [0, 1], width = 2
         3   2            Level 2: positions [0, 3], width = 4 (gap in middle!)
        /     \           
       5       9          Width = rightmost - leftmost + 1 = 3 - 0 + 1 = 4

Even though level 2 has only 2 nodes, its positional width is 4 because positions 0, 1, 2, 3 would exist in a complete tree.

Position Indexing:

We assign positions to nodes as if the tree were complete:

Root: position 0
Left child of node at position p: position 2p + 1
Right child of node at position p: position 2p + 2

(Or using 1-indexed: root = 1, left = 2p, right = 2p + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Finds maximum positional width — horizontal span including gaps.
 * Uses BFS with position tracking.
 * 
 * Position assignment (0-indexed):
 * - Left child of node at pos p: 2*p + 1
 * - Right child of node at pos p: 2*p + 2
 * 
 * Width at a level = rightmost_pos - leftmost_pos + 1
 * 
 * Time: O(n)
 * Space: O(w) for queue
 * 
 * Note: For very deep trees, positions can overflow. Use BigInt
 * or subtract levelMinPos to keep positions small.
 */
function widthOfBinaryTree(root: TreeNode | null): number {
    if (root === null) {
        return 0;
    }
    
    // Queue stores [node, position]
    let queue: Array<[TreeNode, bigint]> = [[root, 0n]];
    let maxWidth = 0n;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        // Get leftmost and rightmost positions at this level
        const leftmostPos = queue[0][1];
        const rightmostPos = queue[queue.length - 1][1];
        
        // Width = span from left to right, inclusive
        const levelWidth = rightmostPos - leftmostPos + 1n;
        if (levelWidth > maxWidth) {
            maxWidth = levelWidth;
        }
        
        // Process level, build next level's queue
        const nextQueue: Array<[TreeNode, bigint]> = [];
        
        for (const [node, pos] of queue) {
            // Normalize positions to prevent overflow
            // By subtracting leftmostPos, we restart counting from 0 each level
            const normalizedPos = pos - leftmostPos;
            
            if (node.left !== null) {
                nextQueue.push([node.left, normalizedPos * 2n + 1n]);
            }
            if (node.right !== null) {
                nextQueue.push([node.right, normalizedPos * 2n + 2n]);
            }
        }
        
        queue = nextQueue;
    }
    
    return Number(maxWidth);
}

Position Overflow — A Real Danger!

Why Track Positions?

Positional width matters for:

Tree visualization (how much horizontal space is needed)
Serialization to array (array size = max width at any level)
Collision detection in tree layouts
Certain geometry problems on trees

Node-count width is simpler but doesn't capture the tree's 'spread'. A tree with all left children has node-count max-width of 1 but effectively spreads across the visualization.

Balanced Tree — Combining Depth Analysis

A balanced binary tree is one where the depth of the two subtrees of every node never differs by more than 1. This ensures O(log n) height, which is critical for efficient tree operations.

Definition:

For every node N: |height(N.left) - height(N.right)| ≤ 1

Why balance matters:

Balanced tree of n nodes: height = O(log n)
Unbalanced tree: height can be O(n)
Operations like search, insert, delete are O(height)
Balanced → O(log n) operations, unbalanced → O(n) operations

Checking Balance:

We need to compute heights AND verify the balance condition at every node. The pattern is similar to diameter — compute a helper value (height) while checking a condition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Determines if a binary tree is height-balanced.
 * A balanced tree has subtree heights differing by at most 1, at every node.
 * 
 * Approach: Compute height recursively, return -1 if unbalanced detected.
 * This allows early termination when imbalance is found.
 * 
 * Time: O(n) - each node visited once
 * Space: O(h) - recursion stack
 */
function isBalanced(root: TreeNode | null): boolean {
    return checkHeight(root) !== -1;
}
 
/**
 * Returns the height of the tree if balanced, or -1 if unbalanced.
 * The -1 serves as a sentinel: "don't bother, there's imbalance below"
 */
function checkHeight(node: TreeNode | null): number {
    // Base case: null has height 0
    if (node === null) {
        return 0;
    }
    
    // Get left subtree height (or -1 if left is unbalanced)
    const leftHeight = checkHeight(node.left);
    if (leftHeight === -1) {
        return -1;  // Left subtree is unbalanced, propagate failure
    }
    
    // Get right subtree height (or -1 if right is unbalanced)
    const rightHeight = checkHeight(node.right);
    if (rightHeight === -1) {
        return -1;  // Right subtree is unbalanced, propagate failure
    }
    
    // Check balance at this node
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;  // This node is unbalanced
    }
    
    // Return height for parent's calculation
    return 1 + Math.max(leftHeight, rightHeight);
}

Why -1 as Sentinel?

Using -1 (invalid height) to signal imbalance allows us to:

Short-circuit computation once imbalance is found
Avoid a separate boolean return value
Keep the recursion clean and O(n)

A naive approach might compute heights separately then compare — this would be O(n log n) for balanced trees due to recomputation.

Alternative: Tuple Return:

function checkBalanced(node: TreeNode | null): [boolean, number] {
    if (node === null) return [true, 0];
    
    const [leftBalanced, leftHeight] = checkBalanced(node.left);
    if (!leftBalanced) return [false, 0];
    
    const [rightBalanced, rightHeight] = checkBalanced(node.right);
    if (!rightBalanced) return [false, 0];
    
    const balanced = Math.abs(leftHeight - rightHeight) <= 1;
    return [balanced, 1 + Math.max(leftHeight, rightHeight)];
}

Both approaches work; the -1 sentinel is more concise.

Practical Applications

Depth and width measurements have direct practical applications across software engineering.

1. Recursion Depth Limits:

Tree height determines recursion stack depth. Languages have limits (often ~1000-10000 calls). Knowing your tree's expected depth helps you decide whether recursive solutions are safe.

2. Memory Allocation:

BFS queue size peaks at tree width. For visualization or processing large trees, knowing max width helps allocate appropriate buffers.

3. Algorithm Selection:

Shallow, wide trees: BFS might have high memory; DFS is safer
Deep, narrow trees: DFS might overflow; iterative BFS is safer
Balanced trees: Either works well

4. Database Query Optimization:

Query execution plans form trees. Plan depth indicates query complexity; balancing the tree (query rewriting) can dramatically improve performance.

5. Parallel Processing:

Tree width indicates parallelization opportunity at each level. Wide levels can be processed in parallel; narrow levels are sequential bottlenecks.

When Depth and Width Matter
Scenario	Key Metric	Why It Matters	Action
Recursive processing	Max depth	Stack overflow risk	Use iterative for deep trees
Level-order processing	Max width	Peak memory usage	Stream processing for wide trees
Tree balancing	Height balance	Operation efficiency	Rebalance if unbalanced
Visualization	Both	Layout dimensions	Allocate appropriate canvas
Serialization	Positional width	Array size for level-order	Pre-allocate array

Complete Binary Tree

Summary and Key Takeaways

Depth and width form the dimensional foundation of tree analysis. Let's consolidate what we've learned:

Core Concepts Mastered

•Max depth (DFS): Simple recursive formula: 1 + max of children depths
•Max depth (BFS): Count levels until queue empties
•Min depth trap: Only leaves count — handle single-child nodes correctly
•Min depth optimization: BFS finds closest leaf first, often faster than DFS
•Width (node count): Use BFS, track queue size per level
•Width (positional): Assign positions; normalize per level to prevent overflow
•Balanced check: Compute height with -1 sentinel for early imbalance detection

DFS vs BFS Decision Framework

Choose DFS when: • Problem is about paths (root-to-leaf, depth-first properties) • Tree structure allows simple recursive formulation • Space is tight and tree is wide

Module Complete:

This concludes Module 9: Common Tree Patterns & Problem Types. You've mastered:

Path Sum Problems — Accumulating values along tree paths
Lowest Common Ancestor — Finding where paths converge
Tree Symmetry & Comparison — Structural analysis and matching
Diameter of a Tree — Finding the longest path anywhere
Maximum Depth & Width — Measuring tree dimensions

These patterns form a toolkit that applies to the vast majority of tree problems. Internalize these patterns, and new tree problems become variations on familiar themes.

Module Complete!