Data Structures & AlgorithmsN-ary Trees & General Tree Structures

N-ary Trees & General Tree Structures

LevelIntermediate

Duration60 mins

TopicN-ary Trees & General Tree Structures

3 / 4

Traversals for N-ary Trees

Visiting Every Node Systematically

Tree traversal—visiting every node in a systematic order—is fundamental to almost every tree algorithm. We've mastered traversals for binary trees: preorder (root-left-right), inorder (left-root-right), postorder (left-right-root), and level-order (breadth-first).

But how do these traversals adapt to N-ary trees, where a node might have zero, three, or twenty children instead of exactly two?

The good news: most traversals generalize naturally. The conceptual framework remains the same—we're just replacing 'left then right' with 'iterate through all children'. However, there's one notable exception that reveals deep structural differences between binary and N-ary trees.

What You Will Learn

You'll master preorder, postorder, and level-order traversals for N-ary trees. You'll understand why in-order traversal doesn't naturally extend to N-ary trees, and you'll implement both recursive and iterative versions of each traversal pattern.

Preorder Traversal: Root First, Then Children

Preorder traversal visits the root before its descendants. For binary trees, this means: root → left → right.

For N-ary trees, the generalization is natural: root → child₀ → child₁ → ... → childₖ₋₁.

We visit the current node first, then recursively traverse all children in order (typically left to right as stored in the children array).

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
interface NaryNode<T> {
    value: T;
    children: NaryNode<T>[];
}
 
// Recursive preorder traversal
function preorderRecursive<T>(root: NaryNode<T> | null): T[] {
    const result: T[] = [];
    
    function traverse(node: NaryNode<T> | null): void {
        if (node === null) return;
        
        // 1. Visit the current node FIRST
        result.push(node.value);
        
        // 2. Then traverse all children in order
        for (const child of node.children) {
            traverse(child);
        }
    }
    
    traverse(root);
    return result;
}
 
// Example tree:
//         A
//       / | \
//      B  C  D
//     /|     |
//    E F     G
 
// Preorder: A, B, E, F, C, D, G
// Pattern: Visit each node, then explore all its subtrees left-to-right

Iterative implementation using explicit stack:

Just as with binary trees, we can eliminate recursion by using an explicit stack. The key insight: we push children onto the stack in reverse order so they're processed left-to-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
function preorderIterative<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const stack: NaryNode<T>[] = [root];
    
    while (stack.length > 0) {
        const node = stack.pop()!;
        
        // Visit the current node
        result.push(node.value);
        
        // Push children in REVERSE order
        // So the first child is processed first (LIFO behavior)
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]);
        }
    }
    
    return result;
}
 
// Why reverse order?
// Stack is LIFO. If children are [B, C, D]:
// - Push D, then C, then B
// - Pop order: B, C, D (correct left-to-right)
//
// Without reversal:
// - Push B, then C, then D
// - Pop order: D, C, B (wrong - right-to-left)

Preorder Applications

Preorder traversal is ideal when you need to process a node before its descendants: creating a copy of a tree, printing a hierarchical structure (like 'tree' command output), serializing a tree for storage, or any operation where parent context is needed before processing children.

Postorder Traversal: Children First, Then Root

Postorder traversal visits the root after all its descendants. For binary trees: left → right → root.

For N-ary trees: child₀ → child₁ → ... → childₖ₋₁ → root.

We recursively traverse all children first, then visit the current node last.

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
// Recursive postorder traversal
function postorderRecursive<T>(root: NaryNode<T> | null): T[] {
    const result: T[] = [];
    
    function traverse(node: NaryNode<T> | null): void {
        if (node === null) return;
        
        // 1. First, traverse all children
        for (const child of node.children) {
            traverse(child);
        }
        
        // 2. Visit the current node LAST
        result.push(node.value);
    }
    
    traverse(root);
    return result;
}
 
// Example tree:
//         A
//       / | \
//      B  C  D
//     /|     |
//    E F     G
 
// Postorder: E, F, B, C, G, D, A
// Pattern: Process all subtrees first, then the node itself

Iterative implementation:

Iterative postorder is trickier than preorder because we need to visit children before parents, but we discover parents first. One elegant approach: do a modified preorder (root, then children right-to-left) and reverse the result.

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
function postorderIterative<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const stack: NaryNode<T>[] = [root];
    
    while (stack.length > 0) {
        const node = stack.pop()!;
        
        // Visit node (but we'll reverse at the end)
        result.push(node.value);
        
        // Push children in NORMAL order (left-to-right)
        // Because we're reversing, this becomes right-to-left in output
        for (const child of node.children) {
            stack.push(child);
        }
    }
    
    // Reverse to get postorder
    return result.reverse();
}
 
// How this works:
// Modified preorder (root, children right-to-left): A, D, G, C, B, F, E
// Reversed: E, F, B, C, G, D, A ← correct postorder!
 
// The insight: 
// Postorder = reverse of (root, children right-to-left)
// Just like binary postorder = reverse of (root, right, left)

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
function postorderTwoStacks<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const stack1: NaryNode<T>[] = [root];
    const stack2: NaryNode<T>[] = [];
    
    // Phase 1: Build stack2 in reverse postorder
    while (stack1.length > 0) {
        const node = stack1.pop()!;
        stack2.push(node);
        
        // Push children to stack1 (they'll be processed next)
        for (const child of node.children) {
            stack1.push(child);
        }
    }
    
    // Phase 2: Pop from stack2 to get postorder
    while (stack2.length > 0) {
        result.push(stack2.pop()!.value);
    }
    
    return result;
}

Postorder Applications

Postorder is essential when you need results from children before processing the parent: computing subtree sizes, calculating directory sizes (file systems), evaluating expression trees, deleting a tree (delete children before parent), or any bottom-up computation.

The Inorder Problem: Where Does the Root Go?

In binary trees, inorder traversal visits nodes in the sequence: left → root → right. The root sits between its two children. This has elegant properties—for Binary Search Trees, inorder produces sorted output.

But for N-ary trees with three or more children, where does the root go?

Binary tree - Inorder is well-defined:
    
      B
     / \
    A   C
    
Inorder: A → B → C  (left, root, right)
Root B sits between its two children.
 
N-ary tree - Where does root go?
 
        B
      / | \
     A  C  D
 
Options:
  A → B → C → D?  (after first child)
  A → C → B → D?  (in the middle)
  A → C → D → B?  (at the end = postorder!)
  
There's no natural "between" position when you have 3+ children!

The fundamental issue:

Inorder traversal's elegance comes from the root being sandwiched between exactly two subtrees. With N-ary trees:

If we put the root after the first child, we get a somewhat arbitrary order
If we put the root in the "middle", odd numbers of children create ambiguity
If we put the root after some fixed number of children, it's no longer symmetric

The conclusion: Inorder traversal doesn't have a natural, universally agreed-upon extension to N-ary trees. Different contexts might define custom "inorder-like" traversals, but there's no canonical version.

Avoid 'N-ary Inorder' Confusion

If you see 'inorder traversal' in the context of N-ary trees, be skeptical. Ask for the precise definition. Some sources define it as 'visit root after first child', others differently. For general N-ary trees, stick to preorder, postorder, and level-order—these have unambiguous semantics.

Special case: N-ary Search Trees

For multi-way search trees like B-trees, there IS a meaningful "inorder" because keys and children alternate. A B-tree node with 3 keys [K₁, K₂, K₃] has 4 children [C₀, C₁, C₂, C₃] where:

All keys in C₀ < K₁
K₁ ≤ all keys in C₁ < K₂
K₂ ≤ all keys in C₂ < K₃
K₃ ≤ all keys in C₃

Inorder for B-trees: traverse(C₀), visit(K₁), traverse(C₁), visit(K₂), traverse(C₂), visit(K₃), traverse(C₃)

This produces sorted output, just like binary BST inorder. But this only works because B-trees have a specific key-child interleaving structure.

Level-Order Traversal: Breadth-First Exploration

Level-order traversal (also called breadth-first traversal) visits all nodes at depth 0, then all at depth 1, then depth 2, and so on. This generalizes to N-ary trees with no changes to the fundamental algorithm—we just enqueue all children instead of just left and 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
function levelOrder<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const queue: NaryNode<T>[] = [root];
    
    while (queue.length > 0) {
        const node = queue.shift()!;  // Dequeue from front
        
        // Visit the current node
        result.push(node.value);
        
        // Enqueue all children (left to right)
        for (const child of node.children) {
            queue.push(child);
        }
    }
    
    return result;
}
 
// Example tree:
//         A
//       / | \
//      B  C  D
//     /|     |
//    E F     G
 
// Level-order: A, B, C, D, E, F, G
// Level 0: A
// Level 1: B, C, D
// Level 2: E, F, G

Level-by-level output:

Often we want output grouped by level (useful for printing, computing width, etc.):

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
function levelOrderGrouped<T>(root: NaryNode<T> | null): T[][] {
    if (root === null) return [];
    
    const result: T[][] = [];
    let currentLevel: NaryNode<T>[] = [root];
    
    while (currentLevel.length > 0) {
        const levelValues: T[] = [];
        const nextLevel: NaryNode<T>[] = [];
        
        for (const node of currentLevel) {
            levelValues.push(node.value);
            
            // Collect children for next level
            for (const child of node.children) {
                nextLevel.push(child);
            }
        }
        
        result.push(levelValues);
        currentLevel = nextLevel;
    }
    
    return result;
}
 
// Example tree result:
// [
//   ["A"],           // Level 0
//   ["B", "C", "D"], // Level 1
//   ["E", "F", "G"]  // Level 2
// ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function maxWidth<T>(root: NaryNode<T> | null): number {
    if (root === null) return 0;
    
    let maxWidth = 0;
    let currentLevel: NaryNode<T>[] = [root];
    
    while (currentLevel.length > 0) {
        // Update max width
        maxWidth = Math.max(maxWidth, currentLevel.length);
        
        // Build next level
        const nextLevel: NaryNode<T>[] = [];
        for (const node of currentLevel) {
            for (const child of node.children) {
                nextLevel.push(child);
            }
        }
        currentLevel = nextLevel;
    }
    
    return maxWidth;
}
 
// For our example tree: max width = 3 (level 1 has B, C, D)

Level-Order Applications

Level-order traversal is essential for: finding shortest paths in unweighted trees, printing trees level-by-level, finding tree width, serializing trees for transmission (BFS order), and any scenario where you need to process 'closer' nodes before 'farther' ones.

Comparing Traversal Orders

Let's solidify understanding by comparing all traversal orders on the same tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Tree Structure:
              1
          /   |   \
         2    3    4
        /|    |   /|\
       5 6   7   8 9 10
 
PREORDER (root, then children left-to-right):
1, 2, 5, 6, 3, 7, 4, 8, 9, 10
  ↳ Visit each node before exploring its subtrees
 
POSTORDER (children left-to-right, then root):
5, 6, 2, 7, 3, 8, 9, 10, 4, 1
  ↳ Visit each node after all its subtrees are processed
 
LEVEL-ORDER (breadth-first):
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  ↳ Visit all nodes at depth d before any at depth d+1
 
INORDER: Not well-defined for N-ary trees!

N-ary Traversal Summary
Traversal	Order	Data Structure	Best For
Preorder	Root → Children	Stack (recursive or explicit)	Copying trees, serialization, printing hierarchy
Postorder	Children → Root	Stack (recursive or explicit)	Deletion, computing sizes, bottom-up calculations
Level-order	Level by level	Queue	Shortest paths, level grouping, width calculation

Time and space complexity:

All traversals visit each node exactly once:

Time: O(n) where n is the number of nodes
Space: O(w) for level-order, where w is maximum width
Space: O(h) for pre/postorder, where h is height (recursion depth or stack depth)

Practical Traversal Applications

Let's see traversals applied to real problems, demonstrating when each order is appropriate:

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 FileNode {
    name: string;
    isDirectory: boolean;
    children: FileNode[];
}
 
// Print tree structure like the 'tree' command
function printDirectoryTree(node: FileNode, indent: string = ""): void {
    // PREORDER: Print this node first
    const prefix = node.isDirectory ? "📁 " : "📄 ";
    console.log(indent + prefix + node.name);
    
    // Then recurse into children
    for (let i = 0; i < node.children.length; i++) {
        const isLast = i === node.children.length - 1;
        const childIndent = indent + (isLast ? "    " : "│   ");
        const branch = isLast ? "└── " : "├── ";
        
        console.log(indent + branch);
        printDirectoryTree(node.children[i], childIndent);
    }
}
 
// Output (preorder traversal):
// 📁 project
// ├── 📄 README.md
// ├── 📁 src
// │   ├── 📄 index.ts
// │   └── 📄 utils.ts
// └── 📁 tests

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
interface FileNodeWithSize {
    name: string;
    size: number;  // File size in bytes (0 for directories)
    children: FileNodeWithSize[];
}
 
// Calculate total size including all descendants
function calculateTotalSize(node: FileNodeWithSize): number {
    // POSTORDER: Calculate children's sizes first
    let totalChildSize = 0;
    for (const child of node.children) {
        totalChildSize += calculateTotalSize(child);
    }
    
    // Then add this node's size
    return node.size + totalChildSize;
}
 
// Example:
// project/
//   ├── README.md (1KB)
//   ├── src/ 
//   │   ├── index.ts (5KB)
//   │   └── utils.ts (3KB)
//   └── package.json (2KB)
//
// calculateTotalSize(project) = 1 + (5 + 3) + 2 = 11KB
// We MUST know src's total size before computing project's total

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
interface Employee {
    name: string;
    title: string;
    directReports: Employee[];
}
 
// Find all employees at a specific management level
function getEmployeesAtLevel(ceo: Employee, targetLevel: number): Employee[] {
    const result: Employee[] = [];
    let currentLevel: Employee[] = [ceo];
    let level = 0;
    
    while (currentLevel.length > 0 && level <= targetLevel) {
        if (level === targetLevel) {
            return currentLevel;  // Found the target level
        }
        
        // Move to next level
        const nextLevel: Employee[] = [];
        for (const employee of currentLevel) {
            for (const report of employee.directReports) {
                nextLevel.push(report);
            }
        }
        currentLevel = nextLevel;
        level++;
    }
    
    return [];  // Target level doesn't exist
}
 
// Level 0: CEO
// Level 1: VPs (direct reports to CEO)
// Level 2: Directors (reports to VPs)
// Level 3: Managers
// ...
 
// getEmployeesAtLevel(ceo, 2) returns all Directors

Choosing the Right Traversal

Ask yourself: 'Do I need to process the parent first, or the children first?' If parent first (copying, printing), use preorder. If children first (size calculation, deletion), use postorder. If you need all nodes at same depth together, use level-order.

Advanced Traversal Patterns

Beyond basic traversals, several advanced patterns arise frequently in N-ary tree problems:

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
// Track the path from root to each node during traversal
function findAllPaths<T>(root: NaryNode<T> | null): T[][] {
    const allPaths: T[][] = [];
    
    function traverse(node: NaryNode<T> | null, currentPath: T[]): void {
        if (node === null) return;
        
        // Add current node to path
        const newPath = [...currentPath, node.value];
        
        // If leaf, this path is complete
        if (node.children.length === 0) {
            allPaths.push(newPath);
            return;
        }
        
        // Otherwise, continue down each child
        for (const child of node.children) {
            traverse(child, newPath);
        }
    }
    
    traverse(root, []);
    return allPaths;
}
 
// For tree:
//       A
//      /|\
//     B C D
//    /|   |
//   E F   G
//
// Returns: [["A","B","E"], ["A","B","F"], ["A","C"], ["A","D","G"]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Process each node with its depth
function traverseWithDepth<T>(
    root: NaryNode<T> | null,
    callback: (node: NaryNode<T>, depth: number) => void
): void {
    function traverse(node: NaryNode<T> | null, depth: number): void {
        if (node === null) return;
        
        callback(node, depth);
        
        for (const child of node.children) {
            traverse(child, depth + 1);
        }
    }
    
    traverse(root, 0);
}
 
// Usage: Print tree with indentation
traverseWithDepth(root, (node, depth) => {
    console.log("  ".repeat(depth) + node.value);
});

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
// Find first node matching a predicate (short-circuit on find)
function findFirst<T>(
    root: NaryNode<T> | null,
    predicate: (value: T) => boolean
): NaryNode<T> | null {
    if (root === null) return null;
    
    // Check current node
    if (predicate(root.value)) {
        return root;
    }
    
    // Check children (short-circuit on first match)
    for (const child of root.children) {
        const found = findFirst(child, predicate);
        if (found !== null) {
            return found;  // Don't check remaining siblings
        }
    }
    
    return null;
}
 
// This is more efficient than collecting all matches
// when you only need the first one

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
// Collect all nodes matching a predicate
function findAll<T>(
    root: NaryNode<T> | null,
    predicate: (value: T) => boolean
): NaryNode<T>[] {
    const results: NaryNode<T>[] = [];
    
    function traverse(node: NaryNode<T> | null): void {
        if (node === null) return;
        
        if (predicate(node.value)) {
            results.push(node);
        }
        
        for (const child of node.children) {
            traverse(child);
        }
    }
    
    traverse(root);
    return results;
}
 
// Usage: Find all nodes with value > 10
const largeNodes = findAll(root, v => v > 10);

Summary: Mastering N-ary Traversals

We've comprehensively covered how traversal algorithms adapt from binary to N-ary trees:

Key Takeaways

•Preorder (root → children) generalizes naturally—visit node, then iterate all children recursively. Use for serialization, copying, printing hierarchies.
•Postorder (children → root) also generalizes naturally—iterate all children recursively, then visit node. Use for deletion, size computation, bottom-up calculations.
•Inorder doesn't generalize because there's no natural 'between' position when nodes have 3+ children. Avoid using 'inorder' for general N-ary trees.
•Level-order uses a queue just like binary trees—enqueue all children instead of just left/right. Use for breadth-first problems, level grouping, width calculations.
•All traversals are O(n) time since each node is visited exactly once.
•Space is O(h) for DFS traversals (recursion/stack depth) and O(w) for BFS (maximum level width).

What's Next:

With traversals mastered, we'll explore the rich landscape of N-ary tree use cases. The next page dives into practical applications: file systems, expression trees, XML/JSON parsing, game scene graphs, and more—showing how N-ary trees power real-world software systems.

Page Complete

You now understand how to systematically traverse every node in an N-ary tree using preorder, postorder, and level-order algorithms. You've seen both recursive and iterative implementations, and you know why inorder doesn't naturally extend. Next, we'll see these trees in action across diverse real-world applications.

3 / 4

Loading learning content...

Data Structures & AlgorithmsN-ary Trees & General Tree Structures

N-ary Trees & General Tree Structures

LevelIntermediate

Duration60 mins

TopicN-ary Trees & General Tree Structures

3 / 4

Traversals for N-ary Trees

Visiting Every Node Systematically

But how do these traversals adapt to N-ary trees, where a node might have zero, three, or twenty children instead of exactly two?

What You Will Learn

Preorder Traversal: Root First, Then Children

Preorder traversal visits the root before its descendants. For binary trees, this means: root → left → right.

For N-ary trees, the generalization is natural: root → child₀ → child₁ → ... → childₖ₋₁.

We visit the current node first, then recursively traverse all children in order (typically left to right as stored in the children array).

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
interface NaryNode<T> {
    value: T;
    children: NaryNode<T>[];
}
 
// Recursive preorder traversal
function preorderRecursive<T>(root: NaryNode<T> | null): T[] {
    const result: T[] = [];
    
    function traverse(node: NaryNode<T> | null): void {
        if (node === null) return;
        
        // 1. Visit the current node FIRST
        result.push(node.value);
        
        // 2. Then traverse all children in order
        for (const child of node.children) {
            traverse(child);
        }
    }
    
    traverse(root);
    return result;
}
 
// Example tree:
//         A
//       / | \
//      B  C  D
//     /|     |
//    E F     G
 
// Preorder: A, B, E, F, C, D, G
// Pattern: Visit each node, then explore all its subtrees left-to-right

Iterative implementation using explicit stack:

Just as with binary trees, we can eliminate recursion by using an explicit stack. The key insight: we push children onto the stack in reverse order so they're processed left-to-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
function preorderIterative<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const stack: NaryNode<T>[] = [root];
    
    while (stack.length > 0) {
        const node = stack.pop()!;
        
        // Visit the current node
        result.push(node.value);
        
        // Push children in REVERSE order
        // So the first child is processed first (LIFO behavior)
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]);
        }
    }
    
    return result;
}
 
// Why reverse order?
// Stack is LIFO. If children are [B, C, D]:
// - Push D, then C, then B
// - Pop order: B, C, D (correct left-to-right)
//
// Without reversal:
// - Push B, then C, then D
// - Pop order: D, C, B (wrong - right-to-left)

Preorder Applications

Postorder Traversal: Children First, Then Root

Postorder traversal visits the root after all its descendants. For binary trees: left → right → root.

For N-ary trees: child₀ → child₁ → ... → childₖ₋₁ → root.

We recursively traverse all children first, then visit the current node last.

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
// Recursive postorder traversal
function postorderRecursive<T>(root: NaryNode<T> | null): T[] {
    const result: T[] = [];
    
    function traverse(node: NaryNode<T> | null): void {
        if (node === null) return;
        
        // 1. First, traverse all children
        for (const child of node.children) {
            traverse(child);
        }
        
        // 2. Visit the current node LAST
        result.push(node.value);
    }
    
    traverse(root);
    return result;
}
 
// Example tree:
//         A
//       / | \
//      B  C  D
//     /|     |
//    E F     G
 
// Postorder: E, F, B, C, G, D, A
// Pattern: Process all subtrees first, then the node itself

Iterative implementation:

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
function postorderIterative<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const stack: NaryNode<T>[] = [root];
    
    while (stack.length > 0) {
        const node = stack.pop()!;
        
        // Visit node (but we'll reverse at the end)
        result.push(node.value);
        
        // Push children in NORMAL order (left-to-right)
        // Because we're reversing, this becomes right-to-left in output
        for (const child of node.children) {
            stack.push(child);
        }
    }
    
    // Reverse to get postorder
    return result.reverse();
}
 
// How this works:
// Modified preorder (root, children right-to-left): A, D, G, C, B, F, E
// Reversed: E, F, B, C, G, D, A ← correct postorder!
 
// The insight: 
// Postorder = reverse of (root, children right-to-left)
// Just like binary postorder = reverse of (root, right, left)

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
function postorderTwoStacks<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const stack1: NaryNode<T>[] = [root];
    const stack2: NaryNode<T>[] = [];
    
    // Phase 1: Build stack2 in reverse postorder
    while (stack1.length > 0) {
        const node = stack1.pop()!;
        stack2.push(node);
        
        // Push children to stack1 (they'll be processed next)
        for (const child of node.children) {
            stack1.push(child);
        }
    }
    
    // Phase 2: Pop from stack2 to get postorder
    while (stack2.length > 0) {
        result.push(stack2.pop()!.value);
    }
    
    return result;
}

Postorder Applications

The Inorder Problem: Where Does the Root Go?

But for N-ary trees with three or more children, where does the root go?

Binary tree - Inorder is well-defined:
    
      B
     / \
    A   C
    
Inorder: A → B → C  (left, root, right)
Root B sits between its two children.
 
N-ary tree - Where does root go?
 
        B
      / | \
     A  C  D
 
Options:
  A → B → C → D?  (after first child)
  A → C → B → D?  (in the middle)
  A → C → D → B?  (at the end = postorder!)
  
There's no natural "between" position when you have 3+ children!

The fundamental issue:

Inorder traversal's elegance comes from the root being sandwiched between exactly two subtrees. With N-ary trees:

If we put the root after the first child, we get a somewhat arbitrary order
If we put the root in the "middle", odd numbers of children create ambiguity
If we put the root after some fixed number of children, it's no longer symmetric

Avoid 'N-ary Inorder' Confusion

Special case: N-ary Search Trees

All keys in C₀ < K₁
K₁ ≤ all keys in C₁ < K₂
K₂ ≤ all keys in C₂ < K₃
K₃ ≤ all keys in C₃

Inorder for B-trees: traverse(C₀), visit(K₁), traverse(C₁), visit(K₂), traverse(C₂), visit(K₃), traverse(C₃)

This produces sorted output, just like binary BST inorder. But this only works because B-trees have a specific key-child interleaving structure.

Level-Order Traversal: Breadth-First Exploration

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
function levelOrder<T>(root: NaryNode<T> | null): T[] {
    if (root === null) return [];
    
    const result: T[] = [];
    const queue: NaryNode<T>[] = [root];
    
    while (queue.length > 0) {
        const node = queue.shift()!;  // Dequeue from front
        
        // Visit the current node
        result.push(node.value);
        
        // Enqueue all children (left to right)
        for (const child of node.children) {
            queue.push(child);
        }
    }
    
    return result;
}
 
// Example tree:
//         A
//       / | \
//      B  C  D
//     /|     |
//    E F     G
 
// Level-order: A, B, C, D, E, F, G
// Level 0: A
// Level 1: B, C, D
// Level 2: E, F, G

Level-by-level output:

Often we want output grouped by level (useful for printing, computing width, etc.):

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
function levelOrderGrouped<T>(root: NaryNode<T> | null): T[][] {
    if (root === null) return [];
    
    const result: T[][] = [];
    let currentLevel: NaryNode<T>[] = [root];
    
    while (currentLevel.length > 0) {
        const levelValues: T[] = [];
        const nextLevel: NaryNode<T>[] = [];
        
        for (const node of currentLevel) {
            levelValues.push(node.value);
            
            // Collect children for next level
            for (const child of node.children) {
                nextLevel.push(child);
            }
        }
        
        result.push(levelValues);
        currentLevel = nextLevel;
    }
    
    return result;
}
 
// Example tree result:
// [
//   ["A"],           // Level 0
//   ["B", "C", "D"], // Level 1
//   ["E", "F", "G"]  // Level 2
// ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function maxWidth<T>(root: NaryNode<T> | null): number {
    if (root === null) return 0;
    
    let maxWidth = 0;
    let currentLevel: NaryNode<T>[] = [root];
    
    while (currentLevel.length > 0) {
        // Update max width
        maxWidth = Math.max(maxWidth, currentLevel.length);
        
        // Build next level
        const nextLevel: NaryNode<T>[] = [];
        for (const node of currentLevel) {
            for (const child of node.children) {
                nextLevel.push(child);
            }
        }
        currentLevel = nextLevel;
    }
    
    return maxWidth;
}
 
// For our example tree: max width = 3 (level 1 has B, C, D)

Level-Order Applications

Comparing Traversal Orders

Let's solidify understanding by comparing all traversal orders on the same tree:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Tree Structure:
              1
          /   |   \
         2    3    4
        /|    |   /|\
       5 6   7   8 9 10
 
PREORDER (root, then children left-to-right):
1, 2, 5, 6, 3, 7, 4, 8, 9, 10
  ↳ Visit each node before exploring its subtrees
 
POSTORDER (children left-to-right, then root):
5, 6, 2, 7, 3, 8, 9, 10, 4, 1
  ↳ Visit each node after all its subtrees are processed
 
LEVEL-ORDER (breadth-first):
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  ↳ Visit all nodes at depth d before any at depth d+1
 
INORDER: Not well-defined for N-ary trees!

N-ary Traversal Summary
Traversal	Order	Data Structure	Best For
Preorder	Root → Children	Stack (recursive or explicit)	Copying trees, serialization, printing hierarchy
Postorder	Children → Root	Stack (recursive or explicit)	Deletion, computing sizes, bottom-up calculations
Level-order	Level by level	Queue	Shortest paths, level grouping, width calculation

Time and space complexity:

All traversals visit each node exactly once:

Time: O(n) where n is the number of nodes
Space: O(w) for level-order, where w is maximum width
Space: O(h) for pre/postorder, where h is height (recursion depth or stack depth)

Practical Traversal Applications

Let's see traversals applied to real problems, demonstrating when each order is appropriate:

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 FileNode {
    name: string;
    isDirectory: boolean;
    children: FileNode[];
}
 
// Print tree structure like the 'tree' command
function printDirectoryTree(node: FileNode, indent: string = ""): void {
    // PREORDER: Print this node first
    const prefix = node.isDirectory ? "📁 " : "📄 ";
    console.log(indent + prefix + node.name);
    
    // Then recurse into children
    for (let i = 0; i < node.children.length; i++) {
        const isLast = i === node.children.length - 1;
        const childIndent = indent + (isLast ? "    " : "│   ");
        const branch = isLast ? "└── " : "├── ";
        
        console.log(indent + branch);
        printDirectoryTree(node.children[i], childIndent);
    }
}
 
// Output (preorder traversal):
// 📁 project
// ├── 📄 README.md
// ├── 📁 src
// │   ├── 📄 index.ts
// │   └── 📄 utils.ts
// └── 📁 tests

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
interface FileNodeWithSize {
    name: string;
    size: number;  // File size in bytes (0 for directories)
    children: FileNodeWithSize[];
}
 
// Calculate total size including all descendants
function calculateTotalSize(node: FileNodeWithSize): number {
    // POSTORDER: Calculate children's sizes first
    let totalChildSize = 0;
    for (const child of node.children) {
        totalChildSize += calculateTotalSize(child);
    }
    
    // Then add this node's size
    return node.size + totalChildSize;
}
 
// Example:
// project/
//   ├── README.md (1KB)
//   ├── src/ 
//   │   ├── index.ts (5KB)
//   │   └── utils.ts (3KB)
//   └── package.json (2KB)
//
// calculateTotalSize(project) = 1 + (5 + 3) + 2 = 11KB
// We MUST know src's total size before computing project's total

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
interface Employee {
    name: string;
    title: string;
    directReports: Employee[];
}
 
// Find all employees at a specific management level
function getEmployeesAtLevel(ceo: Employee, targetLevel: number): Employee[] {
    const result: Employee[] = [];
    let currentLevel: Employee[] = [ceo];
    let level = 0;
    
    while (currentLevel.length > 0 && level <= targetLevel) {
        if (level === targetLevel) {
            return currentLevel;  // Found the target level
        }
        
        // Move to next level
        const nextLevel: Employee[] = [];
        for (const employee of currentLevel) {
            for (const report of employee.directReports) {
                nextLevel.push(report);
            }
        }
        currentLevel = nextLevel;
        level++;
    }
    
    return [];  // Target level doesn't exist
}
 
// Level 0: CEO
// Level 1: VPs (direct reports to CEO)
// Level 2: Directors (reports to VPs)
// Level 3: Managers
// ...
 
// getEmployeesAtLevel(ceo, 2) returns all Directors

Choosing the Right Traversal

Advanced Traversal Patterns

Beyond basic traversals, several advanced patterns arise frequently in N-ary tree problems:

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
// Track the path from root to each node during traversal
function findAllPaths<T>(root: NaryNode<T> | null): T[][] {
    const allPaths: T[][] = [];
    
    function traverse(node: NaryNode<T> | null, currentPath: T[]): void {
        if (node === null) return;
        
        // Add current node to path
        const newPath = [...currentPath, node.value];
        
        // If leaf, this path is complete
        if (node.children.length === 0) {
            allPaths.push(newPath);
            return;
        }
        
        // Otherwise, continue down each child
        for (const child of node.children) {
            traverse(child, newPath);
        }
    }
    
    traverse(root, []);
    return allPaths;
}
 
// For tree:
//       A
//      /|\
//     B C D
//    /|   |
//   E F   G
//
// Returns: [["A","B","E"], ["A","B","F"], ["A","C"], ["A","D","G"]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Process each node with its depth
function traverseWithDepth<T>(
    root: NaryNode<T> | null,
    callback: (node: NaryNode<T>, depth: number) => void
): void {
    function traverse(node: NaryNode<T> | null, depth: number): void {
        if (node === null) return;
        
        callback(node, depth);
        
        for (const child of node.children) {
            traverse(child, depth + 1);
        }
    }
    
    traverse(root, 0);
}
 
// Usage: Print tree with indentation
traverseWithDepth(root, (node, depth) => {
    console.log("  ".repeat(depth) + node.value);
});

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
// Find first node matching a predicate (short-circuit on find)
function findFirst<T>(
    root: NaryNode<T> | null,
    predicate: (value: T) => boolean
): NaryNode<T> | null {
    if (root === null) return null;
    
    // Check current node
    if (predicate(root.value)) {
        return root;
    }
    
    // Check children (short-circuit on first match)
    for (const child of root.children) {
        const found = findFirst(child, predicate);
        if (found !== null) {
            return found;  // Don't check remaining siblings
        }
    }
    
    return null;
}
 
// This is more efficient than collecting all matches
// when you only need the first one

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
// Collect all nodes matching a predicate
function findAll<T>(
    root: NaryNode<T> | null,
    predicate: (value: T) => boolean
): NaryNode<T>[] {
    const results: NaryNode<T>[] = [];
    
    function traverse(node: NaryNode<T> | null): void {
        if (node === null) return;
        
        if (predicate(node.value)) {
            results.push(node);
        }
        
        for (const child of node.children) {
            traverse(child);
        }
    }
    
    traverse(root);
    return results;
}
 
// Usage: Find all nodes with value > 10
const largeNodes = findAll(root, v => v > 10);

Summary: Mastering N-ary Traversals

We've comprehensively covered how traversal algorithms adapt from binary to N-ary trees:

Key Takeaways

•Preorder (root → children) generalizes naturally—visit node, then iterate all children recursively. Use for serialization, copying, printing hierarchies.
•Postorder (children → root) also generalizes naturally—iterate all children recursively, then visit node. Use for deletion, size computation, bottom-up calculations.
•Inorder doesn't generalize because there's no natural 'between' position when nodes have 3+ children. Avoid using 'inorder' for general N-ary trees.
•Level-order uses a queue just like binary trees—enqueue all children instead of just left/right. Use for breadth-first problems, level grouping, width calculations.
•All traversals are O(n) time since each node is visited exactly once.
•Space is O(h) for DFS traversals (recursion/stack depth) and O(w) for BFS (maximum level width).

What's Next:

Page Complete

3 / 4