Tree Properties Height Depth Levels - Learning Module

Loading content...

0/279

Levels and Level-Based Thinking

Thinking Horizontally: Trees as Layers

So far, we've explored trees through vertical measurements: depth (distance from root) and height (distance to leaves). But there's another powerful way to think about trees: as a series of horizontal layers called levels.

Imagine slicing a tree horizontally at each depth value. Each slice contains all nodes at that depth—we call this slice a "level." This perspective transforms how we traverse trees, enabling breadth-first exploration and unlocking solutions to problems that are awkward to solve with depth-first approaches.

What You Will Learn

By the end of this page, you will understand the concept of tree levels, master level-order traversal (BFS), recognize when level-based thinking is the right approach, and solve classic level-based tree problems with confidence.

Defining Levels

A level in a tree is the set of all nodes at the same depth. This simple definition creates a natural horizontal stratification of the tree.

Level k contains all nodes with depth k.

Levels vs Depth

Depth is a property of individual nodes ("this node has depth 3"). Level is a grouping of nodes ("level 3 contains nodes X, Y, Z"). The root is at level 0 (depth 0), its children at level 1 (depth 1), and so on. Level and depth numbers match, but they refer to different concepts—individual measurement vs. collective grouping.

tree-levels-visualization.txt
                    A
                   / \
                  /   \
                 B     C
                / \     \
               D   E     F
              /   / \
             G   H   I
 
    Level Decomposition:
    ═════════════════════════════════════════════════
    Level 0:  [A]           → 1 node   (the root)
    Level 1:  [B, C]        → 2 nodes  (root's children)
    Level 2:  [D, E, F]     → 3 nodes  (grandchildren)
    Level 3:  [G, H, I]     → 3 nodes  (great-grandchildren)
    ═════════════════════════════════════════════════
    
    Tree statistics:
    • Total levels: 4 (levels 0, 1, 2, 3)
    • Tree height: 3 (number of levels minus 1)
    • Level widths: [1, 2, 3, 3]
    • Maximum width: 3 (at levels 2 and 3)

Key properties of levels:

Level numbering starts at 0 — The root is at level 0, matching its depth of 0.
Number of levels = height + 1 — A tree with height h has levels 0 through h, totaling h + 1 levels.
Level width varies — Different levels can have different numbers of nodes. Understanding width distribution matters for space complexity.
In binary trees, level k has at most 2^k nodes — This geometric growth is key to understanding binary tree capacity.
Leaves can appear on multiple levels — Unlike depth-first traversal, level-based traversal encounters leaves at various points.

Level Properties in Binary Trees

Binary trees have specific mathematical properties related to levels that are essential for algorithm analysis.

Maximum Nodes Per Level

In a binary tree, each node has at most 2 children. This creates a geometric progression:

Level	Max Nodes	Total Nodes (cumulative)
0	1	1
1	2	3
2	4	7
3	8	15
k	2^k	2^(k+1) - 1

Tree Capacity and Level Count

These formulas are fundamental:

Maximum nodes at level k: 2^k

Maximum total nodes in tree of height h: 2^(h+1) - 1

Minimum levels to store n nodes: ⌈log₂(n+1)⌉

level-calculations.ts
TypeScript
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
 * Level-related calculations for binary trees.
 */
 
/**
 * Maximum nodes that can exist at a given level in a binary tree.
 */
function maxNodesAtLevel(level: number): number {
    return Math.pow(2, level);
}
 
/**
 * Maximum total nodes in a binary tree of given height.
 * (A complete tree with all levels full)
 */
function maxNodesInTreeOfHeight(height: number): number {
    return Math.pow(2, height + 1) - 1;
}
 
/**
 * Minimum number of levels required to store n nodes.
 */
function minLevelsForNodes(n: number): number {
    if (n <= 0) return 0;
    return Math.ceil(Math.log2(n + 1));
}
 
/**
 * Given n nodes in a complete binary tree, how many are at the last level?
 */
function nodesAtLastLevel(n: number): number {
    const height = Math.floor(Math.log2(n));
    const fullTreeNodes = Math.pow(2, height) - 1;  // Nodes in all full levels
    return n - fullTreeNodes;
}
 
// Demonstrate calculations
function demonstrateLevelCalculations() {
    console.log("Binary Tree Level Calculations");
    console.log("═".repeat(50));
    
    // Level capacity
    console.log("
Max nodes per level:");
    for (let level = 0; level <= 5; level++) {
        console.log(`  Level ${level}: ${maxNodesAtLevel(level).toLocaleString()} nodes`);
    }
    
    // Total capacity
    console.log("
Max total nodes by height:");
    for (let height = 0; height <= 10; height++) {
        const max = maxNodesInTreeOfHeight(height);
        console.log(`  Height ${height.toString().padStart(2)}: ${max.toLocaleString().padStart(10)} nodes`);
    }
    
    // Minimum levels
    console.log("
Minimum levels for n nodes:");
    const nodeCounts = [1, 10, 100, 1000, 10000, 100000, 1000000];
    for (const n of nodeCounts) {
        const levels = minLevelsForNodes(n);
        console.log(`  n = ${n.toLocaleString().padStart(10)}: ${levels} levels`);
    }
}
 
demonstrateLevelCalculations();
 
/* Output:
Binary Tree Level Calculations
══════════════════════════════════════════════════
 
Max nodes per level:
  Level 0: 1 nodes
  Level 1: 2 nodes
  Level 2: 4 nodes
  Level 3: 8 nodes
  Level 4: 16 nodes
  Level 5: 32 nodes
 
Max total nodes by height:
  Height  0:          1 nodes
  Height  1:          3 nodes
  Height  2:          7 nodes
  Height  3:         15 nodes
  Height  4:         31 nodes
  ...
  Height 10:      2,047 nodes
 
Minimum levels for n nodes:
  n =          1: 1 levels
  n =         10: 4 levels
  n =        100: 7 levels
  n =      1,000: 10 levels
  n =     10,000: 14 levels
  n =    100,000: 17 levels
  n =  1,000,000: 20 levels
*/

The Power of Exponential Growth

Each additional level doubles the tree's capacity. A tree of height 10 can hold 2,047 nodes. Height 20 holds over 2 million. Height 30 holds over 2 billion. This exponential growth is why balanced trees with logarithmic height are so efficient—even massive datasets fit in shallow trees.

Level-Order Traversal (Breadth-First Search)

Level-order traversal visits all nodes at level 0, then all at level 1, then level 2, and so on. This is also called Breadth-First Search (BFS) because it explores the tree's "breadth" (width) before its "depth."

This contrasts with depth-first traversals (preorder, inorder, postorder) which dive deep into subtrees before exploring siblings.

The Queue-Based Approach

Level-order traversal uses a queue to maintain the order of nodes to visit:

Start with the root in the queue
While the queue is not empty:
- Dequeue a node and process it
- Enqueue all its children (left first, then right for binary trees)

The queue's FIFO (First-In-First-Out) property ensures nodes are processed in level order.

level-order-traversal.ts
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
interface BinaryTreeNode<T> {
    value: T;
    left: BinaryTreeNode<T> | null;
    right: BinaryTreeNode<T> | null;
}
 
/**
 * Basic level-order traversal: visits nodes level by level.
 * 
 * Time Complexity: O(n) - visits each node exactly once
 * Space Complexity: O(w) - where w is the maximum width (max nodes at any level)
 *                   For a complete binary tree, w ≈ n/2, so O(n) in worst case
 */
function levelOrderTraversal<T>(root: BinaryTreeNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const queue: BinaryTreeNode<T>[] = [root];
    
    while (queue.length > 0) {
        const node = queue.shift()!;  // Dequeue front
        result.push(node.value);      // Process node
        
        // Enqueue children
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    
    return result;
}
 
/**
 * Level-order traversal with level grouping.
 * Returns nodes organized by level: [[level-0], [level-1], ...]
 * 
 * This is extremely useful for many tree problems.
 */
function levelOrderByLevel<T>(root: BinaryTreeNode<T> | null): T[][] {
    if (root === null) return [];
    
    const result: T[][] = [];
    const queue: BinaryTreeNode<T>[] = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;  // Nodes at current level
        const currentLevel: T[] = [];
        
        // Process all nodes at current level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            currentLevel.push(node.value);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
}
 
// Example usage
function demonstrateLevelOrder() {
    // Build tree:       1
    //                  / \
    //                 2   3
    //                / \   \
    //               4   5   6
    
    const tree: BinaryTreeNode<number> = {
        value: 1,
        left: {
            value: 2,
            left: { value: 4, left: null, right: null },
            right: { value: 5, left: null, right: null },
        },
        right: {
            value: 3,
            left: null,
            right: { value: 6, left: null, right: null },
        },
    };
    
    console.log("Flat traversal:", levelOrderTraversal(tree));
    // Output: [1, 2, 3, 4, 5, 6]
    
    console.log("By level:", levelOrderByLevel(tree));
    // Output: [[1], [2, 3], [4, 5, 6]]
}

Queue Implementation Matters

In Python, use collections.deque instead of list for queue operations. list.pop(0) is O(n), making naive BFS O(n²). deque.popleft() is O(1), keeping BFS at O(n). In JavaScript, array.shift() is also O(n) in most engines—consider using a proper queue implementation for large trees.

Level-Order vs Depth-First: When to Use Which

Choosing between level-order (BFS) and depth-first (DFS) traversal depends on the problem structure. Each has distinct advantages.

Use Level-Order (BFS) When

•Finding shortest path in unweighted tree
•Processing nodes by "generation" or layer
•Finding minimum depth to a condition
•Zigzag or alternating level order
•Need to track level boundaries
•Problems involving tree width/diameter at level
•Connecting nodes at same level (cousins)

Use Depth-First (DFS) When

•Computing subtree properties (sum, height)
•Path-based problems (root to leaf)
•Need to maintain path history
•Problems requiring backtracking
•Space is more critical than time
•Tree is very wide but shallow
•Need in-order property (BST)

Space Complexity Comparison

Traversal	Space	Best Case	Worst Case
BFS	O(w) = O(max width)	O(1) for degenerate	O(n/2) for complete
DFS	O(h) = O(height)	O(log n) for complete	O(n) for degenerate

Key insight: BFS uses more space for wide trees, DFS uses more space for deep trees. For balanced trees, DFS (O(log n)) generally uses less space than BFS (O(n/2)).

space-comparison.ts
TypeScript
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
69
70
71
72
73
74
75
76
/**
 * Demonstrates when each traversal type excels.
 */
 
// Problem 1: Find minimum depth (BFS is better)
function minDepthBFS<T>(root: BinaryTreeNode<T> | null): number {
    if (root === null) return -1;
    
    const queue: Array<{ node: BinaryTreeNode<T>; depth: number }> = [
        { node: root, depth: 0 }
    ];
    
    while (queue.length > 0) {
        const { node, depth } = queue.shift()!;
        
        // BFS finds the first leaf = minimum depth
        if (node.left === null && node.right === null) {
            return depth;  // First leaf found is at minimum depth!
        }
        
        if (node.left) queue.push({ node: node.left, depth: depth + 1 });
        if (node.right) queue.push({ node: node.right, depth: depth + 1 });
    }
    
    return -1;
}
 
// Problem 2: Path sum (DFS is better)
function hasPathSum<T extends number>(
    root: BinaryTreeNode<T> | null,
    targetSum: number
): boolean {
    // DFS naturally tracks the path from root
    function dfs(node: BinaryTreeNode<T> | null, remaining: number): boolean {
        if (node === null) return false;
        
        remaining -= node.value;
        
        // Leaf node: check if path sum equals target
        if (node.left === null && node.right === null) {
            return remaining === 0;
        }
        
        // Recurse to children, maintaining running sum
        return dfs(node.left, remaining) || dfs(node.right, remaining);
    }
    
    return dfs(root, targetSum);
}
 
// Problem 3: Level averages (BFS is natural fit)
function levelAverages<T extends number>(
    root: BinaryTreeNode<T> | null
): number[] {
    if (root === null) return [];
    
    const averages: number[] = [];
    const queue: BinaryTreeNode<T>[] = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        let levelSum = 0;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            levelSum += node.value;
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        averages.push(levelSum / levelSize);
    }
    
    return averages;
}

Classic Level-Based Problems

Level-based thinking shines in a category of problems where the horizontal structure of the tree matters. Here are essential patterns:

Problem 1: Binary Tree Right Side View

Given a tree, return the values visible from the right side (last node at each level).

right-side-view.ts
TypeScript
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
/**
 * Returns the rightmost node value at each level.
 * 
 * Approach: Level-order traversal, capture last node of each level.
 */
function rightSideView<T>(root: BinaryTreeNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const queue: BinaryTreeNode<T>[] = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Last node in this level = visible from right
            if (i === levelSize - 1) {
                result.push(node.value);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return result;
}
 
// Alternative: DFS tracking level depth
function rightSideViewDFS<T>(root: BinaryTreeNode<T> | null): T[] {
    const result: T[] = [];
    
    function dfs(node: BinaryTreeNode<T> | null, level: number) {
        if (node === null) return;
        
        // First node we see at this level (going right first) is rightmost
        if (level === result.length) {
            result.push(node.value);
        }
        
        // Visit right first so it's captured first at each level
        dfs(node.right, level + 1);
        dfs(node.left, level + 1);
    }
    
    dfs(root, 0);
    return result;
}

Problem 2: Zigzag Level Order Traversal

Traverse level by level, but alternate direction: left-to-right, right-to-left, left-to-right...

zigzag-traversal.ts
TypeScript
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
/**
 * Zigzag level order traversal.
 * Level 0: left to right
 * Level 1: right to left
 * Level 2: left to right
 * ...
 */
function zigzagLevelOrder<T>(root: BinaryTreeNode<T> | null): T[][] {
    if (root === null) return [];
    
    const result: T[][] = [];
    const queue: BinaryTreeNode<T>[] = [root];
    let leftToRight = true;
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel: T[] = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            
            // Add to front or back based on direction
            if (leftToRight) {
                currentLevel.push(node.value);
            } else {
                currentLevel.unshift(node.value);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
        leftToRight = !leftToRight;  // Toggle direction
    }
    
    return result;
}
 
/*
Example tree:     3
                 / \
                9   20
                   /  \
                  15   7
 
Output: [[3], [20, 9], [15, 7]]
Level 0: [3]        (left to right)
Level 1: [20, 9]    (right to left)
Level 2: [15, 7]    (left to right)
*/

Problem 3: Maximum Width of Binary Tree

Find the maximum width among all levels. Width is the distance between leftmost and rightmost nodes at a level (including nulls in between).

max-width.ts
TypeScript
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
/**
 * Maximum width of binary tree.
 * Width = rightmost position - leftmost position + 1 at any level.
 * 
 * Key insight: Assign positions as if tree were complete binary tree.
 * If parent is at position p, left child is at 2p, right child at 2p+1.
 */
function widthOfBinaryTree<T>(root: BinaryTreeNode<T> | null): number {
    if (root === null) return 0;
    
    let maxWidth = 0;
    // Queue holds [node, position] pairs
    const queue: Array<[BinaryTreeNode<T>, bigint]> = [[root, 0n]];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const levelStart = queue[0][1];  // Position of leftmost node
        let levelEnd = levelStart;       // Will update to rightmost
        
        for (let i = 0; i < levelSize; i++) {
            const [node, pos] = queue.shift()!;
            levelEnd = pos;
            
            // Normalize position to prevent overflow
            // (subtract levelStart so positions stay small)
            const normalizedPos = pos - levelStart;
            
            if (node.left) {
                queue.push([node.left, normalizedPos * 2n]);
            }
            if (node.right) {
                queue.push([node.right, normalizedPos * 2n + 1n]);
            }
        }
        
        const width = Number(levelEnd - levelStart + 1n);
        maxWidth = Math.max(maxWidth, width);
    }
    
    return maxWidth;
}
 
/*
Example:
        1
       / \
      3   2
     / \   \
    5   3   9
 
Level 0: position 0
Level 1: positions 0, 1 → width = 2
Level 2: positions 0, 1, 3 → width = 4 (includes "gap" at position 2)
 
Answer: 4
*/

Level Tracking in DFS

Sometimes you need level information but prefer DFS for its space efficiency or path-tracking capabilities. You can track level as a parameter during DFS traversal.

level-tracking-dfs.ts
TypeScript
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * DFS with level tracking - best of both worlds for some problems.
 */
 
// Pattern: Build level-ordered output using DFS
function levelOrderViaDFS<T>(root: BinaryTreeNode<T> | null): T[][] {
    const result: T[][] = [];
    
    function dfs(node: BinaryTreeNode<T> | null, level: number) {
        if (node === null) return;
        
        // Ensure result has an array for this level
        if (result.length === level) {
            result.push([]);
        }
        
        // Add node to its level's array
        result[level].push(node.value);
        
        // Recurse to children at next level
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    
    dfs(root, 0);
    return result;
}
 
// Problem: Find all nodes at depth K from target
function nodesAtDistanceK<T>(
    root: BinaryTreeNode<T> | null,
    target: BinaryTreeNode<T>,
    k: number
): T[] {
    const result: T[] = [];
    
    // First, find path from root to target and mark parents
    const parentMap = new Map<BinaryTreeNode<T>, BinaryTreeNode<T> | null>();
    
    function buildParentMap(node: BinaryTreeNode<T> | null, parent: BinaryTreeNode<T> | null) {
        if (node === null) return;
        parentMap.set(node, parent);
        buildParentMap(node.left, node);
        buildParentMap(node.right, node);
    }
    
    buildParentMap(root, null);
    
    // BFS from target, treating parent as another neighbor
    const visited = new Set<BinaryTreeNode<T>>();
    const queue: Array<{ node: BinaryTreeNode<T>; dist: number }> = [
        { node: target, dist: 0 }
    ];
    visited.add(target);
    
    while (queue.length > 0) {
        const { node, dist } = queue.shift()!;
        
        if (dist === k) {
            result.push(node.value);
        }
        
        // Explore neighbors: left, right, and parent
        const neighbors = [
            node.left,
            node.right,
            parentMap.get(node)
        ].filter((n): n is BinaryTreeNode<T> => n !== null && n !== undefined);
        
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor) && dist < k) {
                visited.add(neighbor);
                queue.push({ node: neighbor, dist: dist + 1 });
            }
        }
    }
    
    return result;
}
 
// Problem: Deepest leaves sum
function deepestLeavesSum<T extends number>(root: BinaryTreeNode<T> | null): number {
    let maxDepth = 0;
    let sumAtMaxDepth = 0;
    
    function dfs(node: BinaryTreeNode<T> | null, depth: number) {
        if (node === null) return;
        
        // Leaf node
        if (node.left === null && node.right === null) {
            if (depth > maxDepth) {
                maxDepth = depth;
                sumAtMaxDepth = node.value;
            } else if (depth === maxDepth) {
                sumAtMaxDepth += node.value;
            }
            return;
        }
        
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
    
    dfs(root, 0);
    return sumAtMaxDepth;
}

Choosing DFS with Level Tracking

Use DFS with level tracking when: (1) you need O(h) space instead of O(w), (2) you're combining level information with path tracking, (3) you're already doing DFS for another purpose and want level info "for free," or (4) you prefer the recursive programming style.

Using Levels for Tree Analysis

Level-based analysis provides insights into tree structure that path-based analysis cannot easily reveal.

Width at Each Level

Analyzing the number of nodes at each level reveals tree shape and capacity utilization:

level-analysis.ts
TypeScript
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * Compute detailed level statistics for a binary tree.
 */
interface LevelStats {
    level: number;
    nodeCount: number;
    maxPossible: number;
    fillRatio: number;
}
 
function analyzeLevels<T>(root: BinaryTreeNode<T> | null): LevelStats[] {
    if (root === null) return [];
    
    const stats: LevelStats[] = [];
    const queue: BinaryTreeNode<T>[] = [root];
    let level = 0;
    
    while (queue.length > 0) {
        const nodeCount = queue.length;
        const maxPossible = Math.pow(2, level);
        
        stats.push({
            level,
            nodeCount,
            maxPossible,
            fillRatio: nodeCount / maxPossible,
        });
        
        // Process level
        for (let i = 0; i < nodeCount; i++) {
            const node = queue.shift()!;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        level++;
    }
    
    return stats;
}
 
function printTreeAnalysis<T>(root: BinaryTreeNode<T> | null) {
    const stats = analyzeLevels(root);
    const totalNodes = stats.reduce((sum, s) => sum + s.nodeCount, 0);
    const maxWidth = Math.max(...stats.map(s => s.nodeCount));
    const avgWidth = totalNodes / stats.length;
    
    console.log("Tree Level Analysis");
    console.log("═".repeat(50));
    console.log("Level | Nodes | Max Possible | Fill Ratio");
    console.log("─".repeat(50));
    
    for (const s of stats) {
        console.log(
            `  ${s.level.toString().padStart(2)} |   ${s.nodeCount.toString().padStart(3)} |` +
                                        `     ${s.maxPossible.toString().padStart(5)}    |    ${(s.fillRatio * 100).toFixed(0)}%`
        );
    }
    
    console.log("─".repeat(50));
    console.log(`Total nodes: ${totalNodes}`);
    console.log(`Height: ${stats.length - 1}`);
    console.log(`Max width: ${maxWidth}`);
    console.log(`Average width: ${avgWidth.toFixed(1)}`);
    
    // Tree shape classification
    const isComplete = stats.every((s, i) => 
        i === stats.length - 1 || s.fillRatio === 1
    );
    const isDegenerate = stats.every(s => s.nodeCount <= 1);
    
    if (isDegenerate) {
        console.log("Shape: Degenerate (linear)");
    } else if (isComplete) {
        console.log("Shape: Complete");
    } else {
        console.log("Shape: General");
    }
}
 
/*
Example output for a balanced 7-node tree:
 
Tree Level Analysis
══════════════════════════════════════════════════
Level | Nodes | Max Possible | Fill Ratio
──────────────────────────────────────────────────
   0 |     1 |         1    |    100%
   1 |     2 |         2    |    100%
   2 |     4 |         4    |    100%
──────────────────────────────────────────────────
Total nodes: 7
Height: 2
Max width: 4
Average width: 2.3
Shape: Complete
*/

Tree Shape from Level Distribution

Level analysis reveals tree shape: A complete tree has 100% fill ratio at all levels except possibly the last. A degenerate tree has at most 1 node per level. A balanced tree has fill ratios decreasing gradually. This analysis helps diagnose performance issues in tree-based systems.

Summary: Levels and Level-Based Thinking

Levels provide a horizontal perspective on trees, enabling traversal patterns and problem solutions that are awkward with depth-first approaches. Mastering level-based thinking significantly expands your tree problem-solving toolkit.

Key Takeaways

•Levels group nodes by depth — Level k contains all nodes at depth k, creating horizontal "slices" of the tree.
•Level count = height + 1 — A tree of height h has levels 0 through h.
•Binary trees: max 2^k nodes at level k — Geometric growth defines capacity.
•Level-order uses a queue — FIFO ordering ensures breadth-first visitation.
•BFS uses O(width) space, DFS uses O(height) — Choose based on tree shape.
•Level-based patterns solve specific problems — Right side view, zigzag, width, and level grouping.
•DFS can track level too — Pass level as parameter for space-efficient level awareness.

Module Complete:

You've now mastered the three fundamental measurements of tree structures:

Depth — A node's distance from the root (looking up)
Height — A node's distance to its deepest descendant (looking down)
Levels — Grouping nodes by depth (looking across)

These concepts form the foundation for understanding tree operations, analyzing complexity, and choosing appropriate tree structures. In the next module, we'll apply these concepts to explore Binary Trees—the most widely-used tree structure in computer science.

Module Complete

Congratulations! You've completed Module 3: Tree Properties. You now have a solid understanding of depth, height, and levels—the fundamental measurements that govern tree structure and algorithm performance. These concepts will be essential as we explore specific tree types and operations in upcoming modules.