Data Structures & AlgorithmsN-ary Trees & General Tree Structures

N-ary Trees & General Tree Structures

LevelIntermediate

Duration60 mins

TopicN-ary Trees & General Tree Structures

2 / 4

N-ary Tree Representation

From Concept to Code

Understanding that N-ary trees generalize binary trees is one thing. Actually representing them in code is another.

With binary trees, representation is straightforward: every node has left and right pointers. The structure is fixed, predictable, and uniform. But N-ary trees present a challenge: if each node can have any number of children, how do we structure our nodes? How do we store the children? What operations become easy or hard with different choices?

This page explores the fundamental representation strategies for N-ary trees, analyzing trade-offs in memory usage, access patterns, and algorithmic convenience. By the end, you'll be able to choose the right representation for your specific problem.

What You Will Learn

You'll master three core representation strategies: the children-array approach, parent-pointer representation, and the classic left-child right-sibling encoding. You'll understand when each shines, their memory characteristics, and how to implement common operations in each.

The Children Array Representation

The most intuitive representation for N-ary trees stores children in a dynamic array (or list) within each node:

Node = {
    value: T,
    children: List<Node>
}

This directly mirrors our conceptual model: a node has a value and zero or more children. Let's examine this representation in detail.

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
// The most straightforward N-ary tree node
interface NaryNode<T> {
    value: T;
    children: NaryNode<T>[];  // Dynamic array of child nodes
}
 
// Example: Creating a simple N-ary tree
//
//        A
//      / | \
//     B  C  D
//    /|     |
//   E F     G
 
const tree: NaryNode<string> = {
    value: "A",
    children: [
        {
            value: "B",
            children: [
                { value: "E", children: [] },
                { value: "F", children: [] }
            ]
        },
        {
            value: "C",
            children: []  // C is a leaf
        },
        {
            value: "D",
            children: [
                { value: "G", children: [] }
            ]
        }
    ]
};

Characteristics of Children Array Representation:

Operations with Children Array
Operation	Complexity	Notes
Access child by index	O(1)	Direct array indexing: node.children[i]
Get number of children	O(1)	Array length: node.children.length
Add child at end	O(1) amortized	Array push operation
Remove child by index	O(k)	Where k = number of children (array shift)
Find specific child by value	O(k)	Linear search through children
Iterate all children	O(k)	Simple for loop over array
Access parent	O(n) or N/A	Not directly stored; must search tree

Memory Layout:

Each node stores:

The value (size depends on type T)
A reference to the children array
The children array itself (typically: capacity + length + array of references)

For a node with k children, memory usage is approximately:

mem(node) = sizeof(T) + sizeof(array_header) + k * sizeof(pointer)

This is space-efficient in that we only allocate space for actual children. Unlike a binary tree where every node has two pointer slots (even if null), N-ary nodes with children arrays scale with actual child count.

When to Use Children Array

The children array representation is ideal when you frequently iterate over all children, need to access children by index, or when the number of children per node varies significantly. It's the default choice for most N-ary tree implementations.

Common Operations with Children Arrays

Let's implement the fundamental operations that become the building blocks for more complex algorithms:

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
interface NaryNode<T> {
    value: T;
    children: NaryNode<T>[];
}
 
// Check if a node is a leaf
function isLeaf<T>(node: NaryNode<T>): boolean {
    return node.children.length === 0;
}
 
// Count all nodes in the tree (including root)
function size<T>(node: NaryNode<T> | null): number {
    if (node === null) return 0;
    
    // 1 (for this node) + sum of sizes of all subtrees
    let total = 1;
    for (const child of node.children) {
        total += size(child);
    }
    return total;
}
 
// Calculate the height of the tree
function height<T>(node: NaryNode<T> | null): number {
    if (node === null) return -1;  // Empty tree
    if (node.children.length === 0) return 0;  // Leaf
    
    // Height = 1 + max height among all children
    let maxChildHeight = -1;
    for (const child of node.children) {
        maxChildHeight = Math.max(maxChildHeight, height(child));
    }
    return 1 + maxChildHeight;
}
 
// Find a node by value (returns first match)
function find<T>(node: NaryNode<T> | null, target: T): NaryNode<T> | null {
    if (node === null) return null;
    if (node.value === target) return node;
    
    // Search in each subtree
    for (const child of node.children) {
        const found = find(child, target);
        if (found !== null) return found;
    }
    return null;
}
 
// Add a child to a node
function addChild<T>(parent: NaryNode<T>, childValue: T): NaryNode<T> {
    const newChild: NaryNode<T> = { value: childValue, children: [] };
    parent.children.push(newChild);
    return newChild;
}
 
// Count all leaf nodes
function countLeaves<T>(node: NaryNode<T> | null): number {
    if (node === null) return 0;
    if (node.children.length === 0) return 1;  // This is a leaf
    
    let total = 0;
    for (const child of node.children) {
        total += countLeaves(child);
    }
    return total;
}

Key observations:

Recursion is natural — The recursive structure of N-ary trees leads to recursive algorithms. The pattern is consistent: process the current node, then recurse on all children.
For loops replace binary branches — Where binary tree code has recurse(node.left) then recurse(node.right), N-ary tree code has for (const child of node.children) recurse(child).
Base cases are similar — We still check for null nodes and leaf nodes, but leaf detection checks children.length === 0 instead of left === null && right === null.

The Loop-Over-Children Pattern

The loop-over-children pattern is the fundamental building block of N-ary tree algorithms. Once you internalize 'for each child, recurse', most N-ary tree algorithms become straightforward generalizations of their binary counterparts.

Parent Pointer Representation

Sometimes we need to navigate upward in a tree—from a node to its parent, grandparent, or ancestors. With the children-only representation, finding a node's parent requires searching from the root, which is O(n) in the worst case.

The parent pointer representation addresses this by storing a direct reference to each node's parent:

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
// N-ary node with parent pointer
interface NaryNodeWithParent<T> {
    value: T;
    children: NaryNodeWithParent<T>[];
    parent: NaryNodeWithParent<T> | null;  // null for root
}
 
// Creating a tree with parent pointers
function createNode<T>(
    value: T, 
    parent: NaryNodeWithParent<T> | null = null
): NaryNodeWithParent<T> {
    return { value, children: [], parent };
}
 
function addChild<T>(
    parent: NaryNodeWithParent<T>, 
    childValue: T
): NaryNodeWithParent<T> {
    const child = createNode(childValue, parent);  // Set parent reference
    parent.children.push(child);
    return child;
}
 
// Example usage:
const root = createNode("CEO");
const vp1 = addChild(root, "VP Engineering");
const vp2 = addChild(root, "VP Sales");
const manager = addChild(vp1, "Engineering Manager");
const dev = addChild(manager, "Developer");
 
// Now we can navigate upward!
console.log(dev.parent?.value);         // "Engineering Manager"
console.log(dev.parent?.parent?.value); // "VP Engineering"

Operations enabled by parent pointers:

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
// Get the depth of a node (O(d) where d is depth)
function getDepth<T>(node: NaryNodeWithParent<T>): number {
    let depth = 0;
    let current: NaryNodeWithParent<T> | null = node;
    while (current.parent !== null) {
        depth++;
        current = current.parent;
    }
    return depth;
}
 
// Get all ancestors (root to parent, or parent to root)
function getAncestors<T>(node: NaryNodeWithParent<T>): T[] {
    const ancestors: T[] = [];
    let current = node.parent;
    while (current !== null) {
        ancestors.push(current.value);
        current = current.parent;
    }
    return ancestors;  // From parent up to root
}
 
// Find the root from any node
function findRoot<T>(node: NaryNodeWithParent<T>): NaryNodeWithParent<T> {
    let current = node;
    while (current.parent !== null) {
        current = current.parent;
    }
    return current;
}
 
// Find Lowest Common Ancestor (LCA) of two nodes
function findLCA<T>(
    a: NaryNodeWithParent<T>, 
    b: NaryNodeWithParent<T>
): NaryNodeWithParent<T> | null {
    // Collect all ancestors of 'a' into a set
    const ancestorsOfA = new Set<NaryNodeWithParent<T>>();
    let current: NaryNodeWithParent<T> | null = a;
    while (current !== null) {
        ancestorsOfA.add(current);
        current = current.parent;
    }
    
    // Walk up from 'b' until we find a node in ancestorsOfA
    current = b;
    while (current !== null) {
        if (ancestorsOfA.has(current)) {
            return current;
        }
        current = current.parent;
    }
    return null;  // No common ancestor (different trees)
}

The Maintenance Burden

Parent pointers must be maintained when the tree is modified. Adding a child means setting the child's parent. Moving a node means updating parents. Forgetting to update parent pointers creates subtle bugs where navigation returns incorrect results. This is a classic case of trading convenience for maintenance complexity.

Combined Representation: Children + Parent

In practice, many systems use both children arrays and parent pointers, gaining bidirectional navigation at the cost of additional memory and maintenance overhead:

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
class TreeNode<T> {
    value: T;
    children: TreeNode<T>[] = [];
    parent: TreeNode<T> | null = null;
 
    constructor(value: T) {
        this.value = value;
    }
 
    // Safely add a child, maintaining parent pointer
    addChild(childValue: T): TreeNode<T> {
        const child = new TreeNode(childValue);
        child.parent = this;
        this.children.push(child);
        return child;
    }
 
    // Safely remove a child, cleaning parent pointer
    removeChild(child: TreeNode<T>): boolean {
        const index = this.children.indexOf(child);
        if (index === -1) return false;
        
        this.children.splice(index, 1);
        child.parent = null;
        return true;
    }
 
    // Move a subtree to a new parent
    moveTo(newParent: TreeNode<T>): void {
        // Remove from old parent
        if (this.parent) {
            this.parent.removeChild(this);
        }
        // Attach to new parent
        newParent.children.push(this);
        this.parent = newParent;
    }
 
    // Check if this node is an ancestor of another
    isAncestorOf(descendant: TreeNode<T>): boolean {
        let current: TreeNode<T> | null = descendant.parent;
        while (current !== null) {
            if (current === this) return true;
            current = current.parent;
        }
        return false;
    }
 
    // Get the path from root to this node
    pathFromRoot(): T[] {
        const path: T[] = [];
        let current: TreeNode<T> | null = this;
        while (current !== null) {
            path.unshift(current.value);  // Prepend
            current = current.parent;
        }
        return path;
    }
}

Trade-off analysis:

Representation Trade-offs
Representation	Memory per Node	Child Access	Parent Access	Maintenance
Children only	O(k) where k = children	O(1)	O(n) search	Simple
Parent only	O(1)	O(n) search	O(1)	Simple
Children + Parent	O(k) + O(1)	O(1)	O(1)	Complex (bidirectional)

The DOM Uses This Pattern

The web browser's DOM is a classic example of bidirectional N-ary trees. Every DOM node has both childNodes (array of children) and parentNode (reference to parent). This enables both downward traversal (rendering) and upward traversal (event bubbling).

Left-Child Right-Sibling Encoding

There's a classic technique to represent any N-ary tree as a binary tree, called Left-Child Right-Sibling (LCRS) encoding (also known as the first-child next-sibling representation).

The idea:

Each node has exactly two pointers: leftChild and rightSibling
leftChild points to the first child of the node
rightSibling points to the next sibling (the next child of the same parent)

This transforms an N-ary tree into a binary tree using a clever reinterpretation of what 'left' and 'right' mean.

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
Original N-ary Tree:
            A
         /  |  \
        B   C   D
       / \      |
      E   F     G
 
LCRS Binary Encoding:
            A
           /
          B --------> C --------> D
         /                       /
        E --> F                 G
 
Reading the LCRS tree:
- A's leftChild is B (first child)
- B's rightSibling is C (next sibling)
- C's rightSibling is D (next sibling)
- B's leftChild is E (B's first child)
- E's rightSibling is F (E's sibling under B)
- D's leftChild is G (D's first child)
 
To find all children of A:
1. Go to A.leftChild (= B)
2. Follow rightSibling chain: B → C → D → null

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
// Left-Child Right-Sibling representation
interface LCRSNode<T> {
    value: T;
    leftChild: LCRSNode<T> | null;   // First child
    rightSibling: LCRSNode<T> | null; // Next sibling
}
 
// Get all children of a node
function getChildren<T>(node: LCRSNode<T>): LCRSNode<T>[] {
    const children: LCRSNode<T>[] = [];
    let current = node.leftChild;
    while (current !== null) {
        children.push(current);
        current = current.rightSibling;
    }
    return children;
}
 
// Add a child to a node (as last child)
function addChild<T>(parent: LCRSNode<T>, childValue: T): LCRSNode<T> {
    const newChild: LCRSNode<T> = {
        value: childValue,
        leftChild: null,
        rightSibling: null
    };
    
    if (parent.leftChild === null) {
        // No children yet, new child is the first
        parent.leftChild = newChild;
    } else {
        // Navigate to the last sibling
        let lastSibling = parent.leftChild;
        while (lastSibling.rightSibling !== null) {
            lastSibling = lastSibling.rightSibling;
        }
        lastSibling.rightSibling = newChild;
    }
    return newChild;
}
 
// Count children of a node
function countChildren<T>(node: LCRSNode<T>): number {
    let count = 0;
    let current = node.leftChild;
    while (current !== null) {
        count++;
        current = current.rightSibling;
    }
    return count;
}

When is LCRS useful?

Memory-constrained environments — Each node uses exactly two pointers regardless of child count, which is more predictable than dynamic arrays.
Languages without dynamic arrays — In C or assembly, managing variable-length child arrays is complex. LCRS uses fixed-size nodes.
Theoretical analysis — LCRS proves that N-ary tree operations can be performed with binary tree structures, useful for complexity proofs.
Specialized algorithms — Some tree algorithms are designed for binary structures, and LCRS enables applying them to N-ary data.

The Cognitive Cost

LCRS obscures the natural parent-child relationship. 'Iterate children' becomes 'go left once, then follow right chain'. 'Add child' becomes 'go left, traverse all rights, append'. Code is harder to reason about because the structure no longer mirrors the domain.

Implicit Array Representation (Fixed N)

When the maximum number of children N is fixed and small, we can use an implicit array representation similar to how binary heaps are stored. This is particularly useful for complete N-ary trees or trees where we can waste some space for simpler indexing.

Recall that for binary heaps:

Parent of node at index i is at (i-1)/2
Children of node at index i are at 2i+1 and 2i+2

We can generalize this for N-ary heaps:

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
// For an N-ary tree stored in an array:
 
class NaryArrayTree<T> {
    private data: (T | null)[];
    private N: number;  // Maximum children per node
 
    constructor(n: number, capacity: number) {
        this.N = n;
        this.data = new Array(capacity).fill(null);
    }
 
    // Parent of node at index i
    parent(i: number): number {
        if (i === 0) return -1;  // Root has no parent
        return Math.floor((i - 1) / this.N);
    }
 
    // k-th child of node at index i (k = 0, 1, ..., N-1)
    child(i: number, k: number): number {
        return this.N * i + k + 1;
    }
 
    // Get all valid children indices
    children(i: number): number[] {
        const result: number[] = [];
        for (let k = 0; k < this.N; k++) {
            const childIdx = this.child(i, k);
            if (childIdx < this.data.length && this.data[childIdx] !== null) {
                result.push(childIdx);
            }
        }
        return result;
    }
}
 
// Example: A ternary tree (N=3) in an array
//
//            0
//         /  |  \
//        1   2   3
//      / | \
//     4  5  6
//
// Indices:
//   Parent of 4: floor((4-1)/3) = floor(1) = 1 ✓
//   Children of 1: 3*1+1=4, 3*1+2=5, 3*1+3=6 ✓

General formulas for N-ary tree in array:

Operation	Formula
Parent of node i	`⌊(i - 1) / N⌋`
k-th child of node i	`N * i + k + 1` (where k ∈ [0, N-1])
Level of node i	`⌊log_N(i * (N-1) + 1)⌋`

When to use implicit representation:

Complete or nearly-complete N-ary trees (like N-ary heaps)
Fixed maximum branching factor
Cache-friendly access patterns needed
Simple index arithmetic preferred over pointer chasing

D-ary Heaps in Practice

D-ary heaps (heaps with D children) use this representation. For certain values of D, they outperform binary heaps due to reduced height. D=4 is common because it balances height reduction against increased comparison work per level. The implicit array makes parent/child access O(1).

Choosing the Right Representation

With multiple representation options, how do you choose? The decision depends on your access patterns, memory constraints, and domain requirements.

Representation Decision Guide
If You Need...	Use...
Fast iteration over all children	Children array
Index-based child access (3rd child)	Children array
Frequent upward navigation to ancestors	Children + Parent pointers
Finding LCA, computing depths	Parent pointers (at minimum)
Minimal fixed memory per node	LCRS encoding
Complete trees with fixed branching	Implicit array
DOM-like bidirectional traversal	Children + Parent pointers
Simple implementation	Children array only

Children Array: Best For

•File system representations
•DOM/XML document trees
•Organizational hierarchies
•Game scene graphs
•General purpose N-ary trees

Implicit Array: Best For

•D-ary heaps / priority queues
•Complete N-ary trees
•Fixed-structure trees
•Memory-mapped trees
•Cache-optimized access

Start Simple, Add Complexity as Needed

Begin with children arrays only—the simplest representation that matches domain intuition. Add parent pointers only if you actually need upward navigation. Avoid LCRS unless you have specific memory constraints or algorithmic requirements. Premature optimization in tree representation leads to unnecessary complexity.

Summary: Mastering N-ary Representation

We've explored the fundamental ways to represent N-ary trees in code, each with distinct trade-offs:

Key Takeaways

•Children array is the most intuitive representation, directly mirroring conceptual parent-child relationships.
•Parent pointers enable O(1) upward navigation but require careful maintenance during tree modifications.
•Combined representation (children + parent) provides bidirectional navigation at the cost of memory and maintenance complexity.
•LCRS encoding transforms N-ary trees to binary trees using fixed-size nodes—useful for memory constraints or theoretical analysis.
•Implicit array representation works for complete N-ary trees with fixed branching, offering cache-friendly access.
•Choose based on access patterns — the 'best' representation depends on what operations your algorithm needs.

What's Next:

With representation strategies mastered, we'll turn to traversals. How do we systematically visit every node in an N-ary tree? The next page adapts our familiar traversal algorithms—preorder, postorder, and level-order—to work with arbitrary numbers of children.

Page Complete

You now understand the major strategies for representing N-ary trees in code. From children arrays to LCRS encoding, you can choose the right representation for your problem's access patterns and constraints. Next, we'll master traversing these structures systematically.

2 / 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

2 / 4

N-ary Tree Representation

From Concept to Code

Understanding that N-ary trees generalize binary trees is one thing. Actually representing them in code is another.

What You Will Learn

The Children Array Representation

The most intuitive representation for N-ary trees stores children in a dynamic array (or list) within each node:

Node = {
    value: T,
    children: List<Node>
}

This directly mirrors our conceptual model: a node has a value and zero or more children. Let's examine this representation in detail.

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
// The most straightforward N-ary tree node
interface NaryNode<T> {
    value: T;
    children: NaryNode<T>[];  // Dynamic array of child nodes
}
 
// Example: Creating a simple N-ary tree
//
//        A
//      / | \
//     B  C  D
//    /|     |
//   E F     G
 
const tree: NaryNode<string> = {
    value: "A",
    children: [
        {
            value: "B",
            children: [
                { value: "E", children: [] },
                { value: "F", children: [] }
            ]
        },
        {
            value: "C",
            children: []  // C is a leaf
        },
        {
            value: "D",
            children: [
                { value: "G", children: [] }
            ]
        }
    ]
};

Characteristics of Children Array Representation:

Operations with Children Array
Operation	Complexity	Notes
Access child by index	O(1)	Direct array indexing: node.children[i]
Get number of children	O(1)	Array length: node.children.length
Add child at end	O(1) amortized	Array push operation
Remove child by index	O(k)	Where k = number of children (array shift)
Find specific child by value	O(k)	Linear search through children
Iterate all children	O(k)	Simple for loop over array
Access parent	O(n) or N/A	Not directly stored; must search tree

Memory Layout:

Each node stores:

The value (size depends on type T)
A reference to the children array
The children array itself (typically: capacity + length + array of references)

For a node with k children, memory usage is approximately:

mem(node) = sizeof(T) + sizeof(array_header) + k * sizeof(pointer)

When to Use Children Array

Common Operations with Children Arrays

Let's implement the fundamental operations that become the building blocks for more complex algorithms:

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
interface NaryNode<T> {
    value: T;
    children: NaryNode<T>[];
}
 
// Check if a node is a leaf
function isLeaf<T>(node: NaryNode<T>): boolean {
    return node.children.length === 0;
}
 
// Count all nodes in the tree (including root)
function size<T>(node: NaryNode<T> | null): number {
    if (node === null) return 0;
    
    // 1 (for this node) + sum of sizes of all subtrees
    let total = 1;
    for (const child of node.children) {
        total += size(child);
    }
    return total;
}
 
// Calculate the height of the tree
function height<T>(node: NaryNode<T> | null): number {
    if (node === null) return -1;  // Empty tree
    if (node.children.length === 0) return 0;  // Leaf
    
    // Height = 1 + max height among all children
    let maxChildHeight = -1;
    for (const child of node.children) {
        maxChildHeight = Math.max(maxChildHeight, height(child));
    }
    return 1 + maxChildHeight;
}
 
// Find a node by value (returns first match)
function find<T>(node: NaryNode<T> | null, target: T): NaryNode<T> | null {
    if (node === null) return null;
    if (node.value === target) return node;
    
    // Search in each subtree
    for (const child of node.children) {
        const found = find(child, target);
        if (found !== null) return found;
    }
    return null;
}
 
// Add a child to a node
function addChild<T>(parent: NaryNode<T>, childValue: T): NaryNode<T> {
    const newChild: NaryNode<T> = { value: childValue, children: [] };
    parent.children.push(newChild);
    return newChild;
}
 
// Count all leaf nodes
function countLeaves<T>(node: NaryNode<T> | null): number {
    if (node === null) return 0;
    if (node.children.length === 0) return 1;  // This is a leaf
    
    let total = 0;
    for (const child of node.children) {
        total += countLeaves(child);
    }
    return total;
}

Key observations:

Recursion is natural — The recursive structure of N-ary trees leads to recursive algorithms. The pattern is consistent: process the current node, then recurse on all children.
For loops replace binary branches — Where binary tree code has recurse(node.left) then recurse(node.right), N-ary tree code has for (const child of node.children) recurse(child).
Base cases are similar — We still check for null nodes and leaf nodes, but leaf detection checks children.length === 0 instead of left === null && right === null.

The Loop-Over-Children Pattern

Parent Pointer Representation

The parent pointer representation addresses this by storing a direct reference to each node's parent:

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
// N-ary node with parent pointer
interface NaryNodeWithParent<T> {
    value: T;
    children: NaryNodeWithParent<T>[];
    parent: NaryNodeWithParent<T> | null;  // null for root
}
 
// Creating a tree with parent pointers
function createNode<T>(
    value: T, 
    parent: NaryNodeWithParent<T> | null = null
): NaryNodeWithParent<T> {
    return { value, children: [], parent };
}
 
function addChild<T>(
    parent: NaryNodeWithParent<T>, 
    childValue: T
): NaryNodeWithParent<T> {
    const child = createNode(childValue, parent);  // Set parent reference
    parent.children.push(child);
    return child;
}
 
// Example usage:
const root = createNode("CEO");
const vp1 = addChild(root, "VP Engineering");
const vp2 = addChild(root, "VP Sales");
const manager = addChild(vp1, "Engineering Manager");
const dev = addChild(manager, "Developer");
 
// Now we can navigate upward!
console.log(dev.parent?.value);         // "Engineering Manager"
console.log(dev.parent?.parent?.value); // "VP Engineering"

Operations enabled by parent pointers:

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
// Get the depth of a node (O(d) where d is depth)
function getDepth<T>(node: NaryNodeWithParent<T>): number {
    let depth = 0;
    let current: NaryNodeWithParent<T> | null = node;
    while (current.parent !== null) {
        depth++;
        current = current.parent;
    }
    return depth;
}
 
// Get all ancestors (root to parent, or parent to root)
function getAncestors<T>(node: NaryNodeWithParent<T>): T[] {
    const ancestors: T[] = [];
    let current = node.parent;
    while (current !== null) {
        ancestors.push(current.value);
        current = current.parent;
    }
    return ancestors;  // From parent up to root
}
 
// Find the root from any node
function findRoot<T>(node: NaryNodeWithParent<T>): NaryNodeWithParent<T> {
    let current = node;
    while (current.parent !== null) {
        current = current.parent;
    }
    return current;
}
 
// Find Lowest Common Ancestor (LCA) of two nodes
function findLCA<T>(
    a: NaryNodeWithParent<T>, 
    b: NaryNodeWithParent<T>
): NaryNodeWithParent<T> | null {
    // Collect all ancestors of 'a' into a set
    const ancestorsOfA = new Set<NaryNodeWithParent<T>>();
    let current: NaryNodeWithParent<T> | null = a;
    while (current !== null) {
        ancestorsOfA.add(current);
        current = current.parent;
    }
    
    // Walk up from 'b' until we find a node in ancestorsOfA
    current = b;
    while (current !== null) {
        if (ancestorsOfA.has(current)) {
            return current;
        }
        current = current.parent;
    }
    return null;  // No common ancestor (different trees)
}

The Maintenance Burden

Combined Representation: Children + Parent

In practice, many systems use both children arrays and parent pointers, gaining bidirectional navigation at the cost of additional memory and maintenance overhead:

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
class TreeNode<T> {
    value: T;
    children: TreeNode<T>[] = [];
    parent: TreeNode<T> | null = null;
 
    constructor(value: T) {
        this.value = value;
    }
 
    // Safely add a child, maintaining parent pointer
    addChild(childValue: T): TreeNode<T> {
        const child = new TreeNode(childValue);
        child.parent = this;
        this.children.push(child);
        return child;
    }
 
    // Safely remove a child, cleaning parent pointer
    removeChild(child: TreeNode<T>): boolean {
        const index = this.children.indexOf(child);
        if (index === -1) return false;
        
        this.children.splice(index, 1);
        child.parent = null;
        return true;
    }
 
    // Move a subtree to a new parent
    moveTo(newParent: TreeNode<T>): void {
        // Remove from old parent
        if (this.parent) {
            this.parent.removeChild(this);
        }
        // Attach to new parent
        newParent.children.push(this);
        this.parent = newParent;
    }
 
    // Check if this node is an ancestor of another
    isAncestorOf(descendant: TreeNode<T>): boolean {
        let current: TreeNode<T> | null = descendant.parent;
        while (current !== null) {
            if (current === this) return true;
            current = current.parent;
        }
        return false;
    }
 
    // Get the path from root to this node
    pathFromRoot(): T[] {
        const path: T[] = [];
        let current: TreeNode<T> | null = this;
        while (current !== null) {
            path.unshift(current.value);  // Prepend
            current = current.parent;
        }
        return path;
    }
}

Trade-off analysis:

Representation Trade-offs
Representation	Memory per Node	Child Access	Parent Access	Maintenance
Children only	O(k) where k = children	O(1)	O(n) search	Simple
Parent only	O(1)	O(n) search	O(1)	Simple
Children + Parent	O(k) + O(1)	O(1)	O(1)	Complex (bidirectional)

The DOM Uses This Pattern

Left-Child Right-Sibling Encoding

There's a classic technique to represent any N-ary tree as a binary tree, called Left-Child Right-Sibling (LCRS) encoding (also known as the first-child next-sibling representation).

The idea:

Each node has exactly two pointers: leftChild and rightSibling
leftChild points to the first child of the node
rightSibling points to the next sibling (the next child of the same parent)

This transforms an N-ary tree into a binary tree using a clever reinterpretation of what 'left' and 'right' mean.

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
Original N-ary Tree:
            A
         /  |  \
        B   C   D
       / \      |
      E   F     G
 
LCRS Binary Encoding:
            A
           /
          B --------> C --------> D
         /                       /
        E --> F                 G
 
Reading the LCRS tree:
- A's leftChild is B (first child)
- B's rightSibling is C (next sibling)
- C's rightSibling is D (next sibling)
- B's leftChild is E (B's first child)
- E's rightSibling is F (E's sibling under B)
- D's leftChild is G (D's first child)
 
To find all children of A:
1. Go to A.leftChild (= B)
2. Follow rightSibling chain: B → C → D → null

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
// Left-Child Right-Sibling representation
interface LCRSNode<T> {
    value: T;
    leftChild: LCRSNode<T> | null;   // First child
    rightSibling: LCRSNode<T> | null; // Next sibling
}
 
// Get all children of a node
function getChildren<T>(node: LCRSNode<T>): LCRSNode<T>[] {
    const children: LCRSNode<T>[] = [];
    let current = node.leftChild;
    while (current !== null) {
        children.push(current);
        current = current.rightSibling;
    }
    return children;
}
 
// Add a child to a node (as last child)
function addChild<T>(parent: LCRSNode<T>, childValue: T): LCRSNode<T> {
    const newChild: LCRSNode<T> = {
        value: childValue,
        leftChild: null,
        rightSibling: null
    };
    
    if (parent.leftChild === null) {
        // No children yet, new child is the first
        parent.leftChild = newChild;
    } else {
        // Navigate to the last sibling
        let lastSibling = parent.leftChild;
        while (lastSibling.rightSibling !== null) {
            lastSibling = lastSibling.rightSibling;
        }
        lastSibling.rightSibling = newChild;
    }
    return newChild;
}
 
// Count children of a node
function countChildren<T>(node: LCRSNode<T>): number {
    let count = 0;
    let current = node.leftChild;
    while (current !== null) {
        count++;
        current = current.rightSibling;
    }
    return count;
}

When is LCRS useful?

Memory-constrained environments — Each node uses exactly two pointers regardless of child count, which is more predictable than dynamic arrays.
Languages without dynamic arrays — In C or assembly, managing variable-length child arrays is complex. LCRS uses fixed-size nodes.
Theoretical analysis — LCRS proves that N-ary tree operations can be performed with binary tree structures, useful for complexity proofs.
Specialized algorithms — Some tree algorithms are designed for binary structures, and LCRS enables applying them to N-ary data.

The Cognitive Cost

Implicit Array Representation (Fixed N)

Recall that for binary heaps:

Parent of node at index i is at (i-1)/2
Children of node at index i are at 2i+1 and 2i+2

We can generalize this for N-ary heaps:

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
// For an N-ary tree stored in an array:
 
class NaryArrayTree<T> {
    private data: (T | null)[];
    private N: number;  // Maximum children per node
 
    constructor(n: number, capacity: number) {
        this.N = n;
        this.data = new Array(capacity).fill(null);
    }
 
    // Parent of node at index i
    parent(i: number): number {
        if (i === 0) return -1;  // Root has no parent
        return Math.floor((i - 1) / this.N);
    }
 
    // k-th child of node at index i (k = 0, 1, ..., N-1)
    child(i: number, k: number): number {
        return this.N * i + k + 1;
    }
 
    // Get all valid children indices
    children(i: number): number[] {
        const result: number[] = [];
        for (let k = 0; k < this.N; k++) {
            const childIdx = this.child(i, k);
            if (childIdx < this.data.length && this.data[childIdx] !== null) {
                result.push(childIdx);
            }
        }
        return result;
    }
}
 
// Example: A ternary tree (N=3) in an array
//
//            0
//         /  |  \
//        1   2   3
//      / | \
//     4  5  6
//
// Indices:
//   Parent of 4: floor((4-1)/3) = floor(1) = 1 ✓
//   Children of 1: 3*1+1=4, 3*1+2=5, 3*1+3=6 ✓

General formulas for N-ary tree in array:

Operation	Formula
Parent of node i	`⌊(i - 1) / N⌋`
k-th child of node i	`N * i + k + 1` (where k ∈ [0, N-1])
Level of node i	`⌊log_N(i * (N-1) + 1)⌋`

When to use implicit representation:

Complete or nearly-complete N-ary trees (like N-ary heaps)
Fixed maximum branching factor
Cache-friendly access patterns needed
Simple index arithmetic preferred over pointer chasing

D-ary Heaps in Practice

Choosing the Right Representation

With multiple representation options, how do you choose? The decision depends on your access patterns, memory constraints, and domain requirements.

Representation Decision Guide
If You Need...	Use...
Fast iteration over all children	Children array
Index-based child access (3rd child)	Children array
Frequent upward navigation to ancestors	Children + Parent pointers
Finding LCA, computing depths	Parent pointers (at minimum)
Minimal fixed memory per node	LCRS encoding
Complete trees with fixed branching	Implicit array
DOM-like bidirectional traversal	Children + Parent pointers
Simple implementation	Children array only

Children Array: Best For

•File system representations
•DOM/XML document trees
•Organizational hierarchies
•Game scene graphs
•General purpose N-ary trees

Implicit Array: Best For

•D-ary heaps / priority queues
•Complete N-ary trees
•Fixed-structure trees
•Memory-mapped trees
•Cache-optimized access

Start Simple, Add Complexity as Needed

Summary: Mastering N-ary Representation

We've explored the fundamental ways to represent N-ary trees in code, each with distinct trade-offs:

Key Takeaways

•Children array is the most intuitive representation, directly mirroring conceptual parent-child relationships.
•Parent pointers enable O(1) upward navigation but require careful maintenance during tree modifications.
•Combined representation (children + parent) provides bidirectional navigation at the cost of memory and maintenance complexity.
•LCRS encoding transforms N-ary trees to binary trees using fixed-size nodes—useful for memory constraints or theoretical analysis.
•Implicit array representation works for complete N-ary trees with fixed branching, offering cache-friendly access.
•Choose based on access patterns — the 'best' representation depends on what operations your algorithm needs.

What's Next:

Page Complete

2 / 4