Data Structures & AlgorithmsN-ary Trees & General Tree Structures

N-ary Trees & General Tree Structures

LevelIntermediate

Duration60 mins

TopicN-ary Trees & General Tree Structures

4 / 4

Use Cases — File Systems, Expression Trees, and Beyond

N-ary Trees in the Wild

N-ary trees aren't abstract academic constructs—they're the backbone of countless software systems you interact with daily. Every time you browse files on your computer, view a web page, navigate a menu, or play a video game, you're working with N-ary tree structures.

This page explores the major real-world applications of N-ary trees, demonstrating how the concepts we've learned translate into production software. We'll examine file systems, document object models, organizational hierarchies, game engines, and expression parsers—each revealing different facets of N-ary tree power.

What You Will Learn

You'll see N-ary trees applied to file system navigation, DOM manipulation, org chart analysis, game scene graph rendering, and expression tree evaluation. Each use case will highlight specific traversal patterns, representation choices, and algorithmic techniques tailored to the domain.

File Systems: The Quintessential N-ary Tree

File systems are perhaps the most intuitive example of N-ary trees. Every operating system—Windows, macOS, Linux—organizes files into a hierarchical directory structure:

The root directory (C:\ on Windows, / on Unix) is the tree's root node
Directories are internal nodes that can contain any number of children
Files are leaf nodes (they have no children)

This structure admits all the operations we've studied: traversal, search, size computation, and more.

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
interface FileSystemNode {
    name: string;
    type: "file" | "directory";
    size: number;          // File size in bytes (0 for directories)
    modifiedAt: Date;
    children: FileSystemNode[];  // Empty array for files
}
 
// Example structure:
const projectDir: FileSystemNode = {
    name: "my-project",
    type: "directory",
    size: 0,
    modifiedAt: new Date("2024-01-15"),
    children: [
        {
            name: "README.md",
            type: "file",
            size: 2048,
            modifiedAt: new Date("2024-01-14"),
            children: []
        },
        {
            name: "src",
            type: "directory",
            size: 0,
            modifiedAt: new Date("2024-01-15"),
            children: [
                {
                    name: "index.ts",
                    type: "file",
                    size: 5120,
                    modifiedAt: new Date("2024-01-15"),
                    children: []
                },
                {
                    name: "utils.ts",
                    type: "file",
                    size: 3072,
                    modifiedAt: new Date("2024-01-13"),
                    children: []
                }
            ]
        },
        {
            name: "package.json",
            type: "file",
            size: 1024,
            modifiedAt: new Date("2024-01-10"),
            children: []
        }
    ]
};

Common file system operations as tree 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
67
68
69
70
71
72
73
74
75
76
77
// 1. Calculate total directory size (POSTORDER)
function getDirectorySize(node: FileSystemNode): number {
    if (node.type === "file") {
        return node.size;
    }
    
    // Directory: sum of all children's sizes
    let total = 0;
    for (const child of node.children) {
        total += getDirectorySize(child);
    }
    return total;
}
 
// 2. Find all files matching a pattern (PREORDER with filter)
function findFiles(
    node: FileSystemNode, 
    pattern: RegExp
): FileSystemNode[] {
    const results: FileSystemNode[] = [];
    
    function search(current: FileSystemNode): void {
        if (current.type === "file" && pattern.test(current.name)) {
            results.push(current);
        }
        
        for (const child of current.children) {
            search(child);
        }
    }
    
    search(node);
    return results;
}
 
// Usage: Find all TypeScript files
const tsFiles = findFiles(projectDir, /\.tsx?$/);
 
// 3. Get the path to a specific file (search with path tracking)
function findPath(
    node: FileSystemNode, 
    targetName: string,
    currentPath: string = ""
): string | null {
    const nodePath = currentPath + "/" + node.name;
    
    if (node.name === targetName) {
        return nodePath;
    }
    
    for (const child of node.children) {
        const found = findPath(child, targetName, nodePath);
        if (found !== null) return found;
    }
    
    return null;
}
 
// Usage: findPath(projectDir, "utils.ts") 
// Returns: "/my-project/src/utils.ts"
 
// 4. List directory contents at depth (LEVEL-ORDER)
function listAtDepth(node: FileSystemNode, depth: number): string[] {
    let currentLevel = [node];
    let currentDepth = 0;
    
    while (currentLevel.length > 0 && currentDepth < depth) {
        const nextLevel: FileSystemNode[] = [];
        for (const n of currentLevel) {
            nextLevel.push(...n.children);
        }
        currentLevel = nextLevel;
        currentDepth++;
    }
    
    return currentLevel.map(n => n.name);
}

Real File System Commands

Commands like 'du' (disk usage) use postorder traversal to compute sizes bottom-up. 'find' uses preorder traversal with filtering. 'tree' uses preorder with depth tracking for indentation. These aren't arbitrary—the traversal order matches the operation semantics.

Document Object Model: Web Page Structure

When you load a web page, the browser parses HTML and constructs a Document Object Model (DOM)—an N-ary tree representing the page structure. Every HTML element becomes a node, with child elements as children nodes.

The DOM is the interface between JavaScript and the page content. Understanding it as an N-ary tree illuminates how DOM manipulation works.

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
<!-- HTML Source -->
<html>
  <head>
    <title>My Page</title>
    <style>/* styles */</style>
  </head>
  <body>
    <header>
      <nav>
        <a href="/">Home</a>
        <a href="/about">About</a>
      </nav>
    </header>
    <main>
      <article>
        <h1>Welcome</h1>
        <p>Content here...</p>
      </article>
    </main>
  </body>
</html>
 
<!-- 
DOM Tree Structure:
html (root)
├── head
│   ├── title ("My Page")
│   └── style
└── body
    ├── header
    │   └── nav
    │       ├── a ("Home")
    │       └── a ("About")
    └── main
        └── article
            ├── h1 ("Welcome")
            └── p ("Content here...")
-->

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
// The DOM provides N-ary tree navigation built-in:
 
// Accessing children (returns live NodeList)
const children = element.childNodes;      // All child nodes
const elements = element.children;        // Only element children
 
// Parent access
const parent = element.parentNode;
const parentElement = element.parentElement;
 
// Sibling access (like LCRS right pointer!)
const nextSib = element.nextSibling;
const prevSib = element.previousSibling;
 
// Example: Count all elements in a subtree (preorder traversal)
function countElements(root: Element): number {
    let count = 1;  // Count this element
    
    for (const child of root.children) {
        count += countElements(child);
    }
    
    return count;
}
 
// Example: Find all elements with a specific class
function findByClass(root: Element, className: string): Element[] {
    const results: Element[] = [];
    
    if (root.classList.contains(className)) {
        results.push(root);
    }
    
    for (const child of root.children) {
        results.push(...findByClass(child, className));
    }
    
    return results;
}
 
// (In practice, use querySelector/querySelectorAll which do this internally)

Key DOM operations as tree algorithms:

DOM Operation	Tree Algorithm	Traversal Type
`getElementById()`	Search tree	Preorder (early exit)
`getElementsByTagName()`	Filter + collect	Preorder
`querySelector()`	CSS selector match	Preorder
`innerHTML` get	Serialize subtree	Preorder
`remove()`	Delete subtree	Postorder (detach children first)
Render layout	Compute sizes	Postorder (children before parent)
Event bubbling	Walk to root	Follow parent pointers

Virtual DOM in React

React's Virtual DOM is also an N-ary tree. React's reconciliation algorithm compares two trees (old and new virtual DOM) to compute minimal updates. This 'tree diff' algorithm leverages the tree structure for efficient updates—a sophisticated application of N-ary tree algorithms.

XML and JSON: Data as Trees

XML and JSON are hierarchical data formats that naturally map to N-ary trees. Parsers convert text into tree structures, and serializers convert trees back to text.

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
{
  "company": {
    "name": "TechCorp",
    "departments": [
      {
        "name": "Engineering",
        "teams": [
          { "name": "Backend", "headcount": 15 },
          { "name": "Frontend", "headcount": 10 },
          { "name": "DevOps", "headcount": 5 }
        ]
      },
      {
        "name": "Sales",
        "teams": [
          { "name": "Enterprise", "headcount": 20 },
          { "name": "SMB", "headcount": 12 }
        ]
      }
    ]
  }
}
 
// This JSON forms a tree:
// company (root)
// ├── name: "TechCorp"
// └── departments (array → internal node)
//     ├── Engineering
//     │   ├── name: "Engineering"
//     │   └── teams (array)
//     │       ├── { Backend, 15 }
//     │       ├── { Frontend, 10 }
//     │       └── { DevOps, 5 }
//     └── Sales
//         ├── name: "Sales"
//         └── teams (array)
//             ├── { Enterprise, 20 }
//             └── { SMB, 12 }

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
// Generic JSON value type
type JsonValue = 
    | string 
    | number 
    | boolean 
    | null 
    | JsonValue[] 
    | { [key: string]: JsonValue };
 
// Traverse all nodes in a JSON structure
function traverseJson(
    value: JsonValue,
    callback: (path: string[], value: JsonValue) => void,
    path: string[] = []
): void {
    callback(path, value);
    
    if (Array.isArray(value)) {
        // Array: children are indexed elements
        value.forEach((item, index) => {
            traverseJson(item, callback, [...path, String(index)]);
        });
    } else if (value !== null && typeof value === "object") {
        // Object: children are key-value pairs
        for (const [key, child] of Object.entries(value)) {
            traverseJson(child, callback, [...path, key]);
        }
    }
    // Primitives (string, number, boolean, null) are leaves
}
 
// Usage: Find all paths to numeric values
const numericPaths: string[][] = [];
traverseJson(data, (path, value) => {
    if (typeof value === "number") {
        numericPaths.push(path);
    }
});
 
// Result: [
//   ["company", "departments", "0", "teams", "0", "headcount"],
//   ["company", "departments", "0", "teams", "1", "headcount"],
//   ...
// ]

XML processing patterns:

XML uses two main parsing approaches:

DOM parsing — Build the entire tree in memory, then traverse. Good for small-to-medium documents where you need random access.
SAX/StAX parsing — Stream through the document, firing events (start element, end element, text). Never builds full tree. Good for huge documents or when you only need specific data.

Both approaches treat XML as a tree—DOM explicitly builds it, SAX implicitly traverses it via events.

Organizational Hierarchies: People Trees

Corporate organizational structures are classic N-ary trees. A CEO has VPs reporting to them, VPs have directors, directors have managers, and so on. This hierarchy enables many HR analytics operations.

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
interface Employee {
    id: string;
    name: string;
    title: string;
    salary: number;
    hireDate: Date;
    directReports: Employee[];
}
 
// Find total compensation under a manager (POSTORDER)
function getTotalCompensation(employee: Employee): number {
    let total = employee.salary;
    
    for (const report of employee.directReports) {
        total += getTotalCompensation(report);
    }
    
    return total;
}
 
// Count team size including all nested reports (POSTORDER)
function getTeamSize(employee: Employee): number {
    let size = 1;  // Count self
    
    for (const report of employee.directReports) {
        size += getTeamSize(report);
    }
    
    return size;
}
 
// Find the management chain (root to this employee)
function getManagementChain(
    root: Employee, 
    targetId: string
): Employee[] | null {
    if (root.id === targetId) {
        return [root];
    }
    
    for (const report of root.directReports) {
        const chain = getManagementChain(report, targetId);
        if (chain !== null) {
            return [root, ...chain];  // Prepend current manager
        }
    }
    
    return null;
}
 
// Find common manager of two employees (LCA problem!)
function findCommonManager(
    root: Employee,
    id1: string,
    id2: string
): Employee | null {
    // Check if this subtree contains the target
    function contains(emp: Employee, targetId: string): boolean {
        if (emp.id === targetId) return true;
        return emp.directReports.some(r => contains(r, targetId));
    }
    
    // If both targets are in this subtree
    if (!contains(root, id1) || !contains(root, id2)) {
        return null;
    }
    
    // If root is one of the targets
    if (root.id === id1 || root.id === id2) {
        return root;
    }
    
    // Count how many children contain either target
    const containingChildren = root.directReports.filter(
        r => contains(r, id1) || contains(r, id2)
    );
    
    if (containingChildren.length === 2) {
        // Targets are in different subtrees; root is LCA
        return root;
    } else if (containingChildren.length === 1) {
        // Both targets in same subtree; recurse
        return findCommonManager(containingChildren[0], id1, id2);
    }
    
    return null;
}
 
// Get org depth (management levels)
function getOrgDepth(root: Employee): number {
    if (root.directReports.length === 0) return 0;
    
    let maxDepth = 0;
    for (const report of root.directReports) {
        maxDepth = Math.max(maxDepth, getOrgDepth(report));
    }
    
    return 1 + maxDepth;
}

HR Analytics Use Cases

Real HR systems use these tree operations for: span-of-control analysis (how many reports per manager), budget rollups (total compensation per division), succession planning (who reports to whom), and diversity analytics (demographics at each level). The tree structure makes these queries natural.

Game Scene Graphs: Rendering Hierarchies

In game development and 3D graphics, scene graphs organize objects hierarchically. A car has wheels as children; a wheel has tire and rim as children. When the car moves, all descendants move with it. This parent-child relationship enables efficient transform propagation.

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
interface Transform {
    position: { x: number; y: number; z: number };
    rotation: { x: number; y: number; z: number };
    scale: { x: number; y: number; z: number };
}
 
interface SceneNode {
    name: string;
    localTransform: Transform;     // Relative to parent
    worldTransform?: Transform;    // Computed absolute position
    mesh?: string;                 // Reference to renderable mesh
    children: SceneNode[];
}
 
// Example: A robot arm
const robotArm: SceneNode = {
    name: "RobotArm",
    localTransform: { 
        position: { x: 0, y: 0, z: 0 },
        rotation: { x: 0, y: 0, z: 0 },
        scale: { x: 1, y: 1, z: 1 }
    },
    children: [
        {
            name: "Shoulder",
            localTransform: { 
                position: { x: 0, y: 1, z: 0 },
                rotation: { x: 0, y: 0, z: 0 },
                scale: { x: 1, y: 1, z: 1 }
            },
            mesh: "shoulder_mesh",
            children: [
                {
                    name: "Elbow",
                    localTransform: { 
                        position: { x: 0, y: 1.5, z: 0 },
                        rotation: { x: 0, y: 0, z: 0 },
                        scale: { x: 1, y: 1, z: 1 }
                    },
                    mesh: "elbow_mesh",
                    children: [
                        {
                            name: "Hand",
                            localTransform: { 
                                position: { x: 0, y: 1, z: 0 },
                                rotation: { x: 0, y: 0, z: 0 },
                                scale: { x: 1, y: 1, z: 1 }
                            },
                            mesh: "hand_mesh",
                            children: []
                        }
                    ]
                }
            ]
        }
    ]
};

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
// Update world transforms - PREORDER traversal
// Parents must be updated before children!
function updateWorldTransforms(
    node: SceneNode, 
    parentWorld: Transform
): void {
    // Compute this node's world transform
    // (simplified - real implementation uses matrix multiplication)
    node.worldTransform = combineTransforms(parentWorld, node.localTransform);
    
    // Update children with this node's world transform
    for (const child of node.children) {
        updateWorldTransforms(child, node.worldTransform);
    }
}
 
function combineTransforms(parent: Transform, local: Transform): Transform {
    return {
        position: {
            x: parent.position.x + local.position.x * parent.scale.x,
            y: parent.position.y + local.position.y * parent.scale.y,
            z: parent.position.z + local.position.z * parent.scale.z,
        },
        rotation: {
            x: parent.rotation.x + local.rotation.x,
            y: parent.rotation.y + local.rotation.y,
            z: parent.rotation.z + local.rotation.z,
        },
        scale: {
            x: parent.scale.x * local.scale.x,
            y: parent.scale.y * local.scale.y,
            z: parent.scale.z * local.scale.z,
        }
    };
}
 
// Render scene - PREORDER (could also use painters algorithm)
function render(node: SceneNode): void {
    if (node.mesh && node.worldTransform) {
        drawMesh(node.mesh, node.worldTransform);
    }
    
    for (const child of node.children) {
        render(child);
    }
}
 
function drawMesh(meshId: string, transform: Transform): void {
    console.log(`Rendering ${meshId} at position ${JSON.stringify(transform.position)}`);
    // Actual GPU rendering calls here
}

Why scene graphs use N-ary trees:

Transform inheritance — Children inherit parent transforms. Moving a car moves its wheels automatically.
Grouped manipulation — Select a character node, transform the entire character including all body parts.
Culling optimization — If a parent is outside the camera view, skip rendering all children.
Animation systems — Skeletal animation applies rotations to parent bones, children follow.
Level of detail — Replace entire subtrees with simpler versions based on distance.

Expression Trees: Parsing and Evaluation

Expression trees represent mathematical or logical expressions in tree form. While simple arithmetic uses binary trees (each operator has two operands), many real expressions are N-ary:

Function calls: max(a, b, c, d) has 4 arguments
Variable-arity operators: sum(1, 2, 3, 4, 5) could take any number
List literals: [1, 2, 3, 4]
Method chains: object.method1().method2().method3()

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
type ExprNode = 
    | { type: "number"; value: number }
    | { type: "variable"; name: string }
    | { type: "binary"; operator: "+" | "-" | "*" | "/"; left: ExprNode; right: ExprNode }
    | { type: "function"; name: string; args: ExprNode[] };  // N-ary!
 
// Example: max(x + 1, y * 2, 10)
const expr: ExprNode = {
    type: "function",
    name: "max",
    args: [
        {
            type: "binary",
            operator: "+",
            left: { type: "variable", name: "x" },
            right: { type: "number", value: 1 }
        },
        {
            type: "binary",
            operator: "*",
            left: { type: "variable", name: "y" },
            right: { type: "number", value: 2 }
        },
        { type: "number", value: 10 }
    ]
};
 
// Tree structure:
//            max (function, 3 children)
//           / |  \
//          +  *   10
//         /| /\
//        x 1 y 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
type Environment = Map<string, number>;
 
const builtinFunctions: Record<string, (...args: number[]) => number> = {
    max: (...args) => Math.max(...args),
    min: (...args) => Math.min(...args),
    sum: (...args) => args.reduce((a, b) => a + b, 0),
    avg: (...args) => args.reduce((a, b) => a + b, 0) / args.length,
};
 
function evaluate(expr: ExprNode, env: Environment): number {
    switch (expr.type) {
        case "number":
            return expr.value;
            
        case "variable":
            const val = env.get(expr.name);
            if (val === undefined) {
                throw new Error(`Undefined variable: ${expr.name}`);
            }
            return val;
            
        case "binary":
            // POSTORDER: evaluate children (operands) first
            const left = evaluate(expr.left, env);
            const right = evaluate(expr.right, env);
            switch (expr.operator) {
                case "+": return left + right;
                case "-": return left - right;
                case "*": return left * right;
                case "/": return left / right;
            }
            
        case "function":
            // POSTORDER: evaluate all arguments first
            const argValues = expr.args.map(arg => evaluate(arg, env));
            
            const fn = builtinFunctions[expr.name];
            if (!fn) {
                throw new Error(`Unknown function: ${expr.name}`);
            }
            return fn(...argValues);
    }
}
 
// Usage
const env = new Map([["x", 5], ["y", 3]]);
const result = evaluate(expr, env);
// max(5 + 1, 3 * 2, 10) = max(6, 6, 10) = 10

AST in Compilers

Programming language compilers build Abstract Syntax Trees (ASTs)—N-ary expression trees representing the entire program. Statements, expressions, declarations, and control flow all become tree nodes. Optimization passes and code generation traverse these trees, typically in postorder for evaluation semantics.

Additional N-ary Tree Applications

Beyond the detailed examples above, N-ary trees appear in many other contexts:

More N-ary Tree Applications
Application	Tree Structure	Key Operations
Menu Systems	Menu → Submenus → Items	Navigation, highlight tracking, keyboard traversal
Taxonomies	Kingdom → Phylum → Class → ...	Classification, nearest common ancestor
Comment Threads	Post → Replies → Nested Replies	Chronological sorting, depth limiting, collapse/expand
Decision Trees (ML)	Feature tests → outcomes	Prediction (preorder), training (postorder metrics)
Trie (Prefix Trees)	Root → characters → ...	Autocomplete, spell check, IP routing
B-Trees / B+Trees	Keys with many children	Database indexing, disk-based storage
Category Hierarchies	Top Category → Subcategories	E-commerce navigation, content organization
Undo History (branching)	State → alternative futures	Version control, document editing

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 Comment {
    id: string;
    author: string;
    text: string;
    timestamp: Date;
    replies: Comment[];  // N-ary: any number of replies
}
 
// Render comments with proper nesting (preorder)
function renderComments(comments: Comment[], depth: number = 0): void {
    for (const comment of comments) {
        const indent = "  ".repeat(depth);
        console.log(`${indent}[${comment.author}]: ${comment.text}`);
        
        // Recursively render replies
        renderComments(comment.replies, depth + 1);
    }
}
 
// Count total comments including all nested replies
function countAllComments(comments: Comment[]): number {
    let count = comments.length;
    for (const comment of comments) {
        count += countAllComments(comment.replies);
    }
    return count;
}
 
// Find deepest comment level
function maxCommentDepth(comments: Comment[]): number {
    if (comments.length === 0) return 0;
    
    let maxChildDepth = 0;
    for (const comment of comments) {
        maxChildDepth = Math.max(maxChildDepth, maxCommentDepth(comment.replies));
    }
    return 1 + maxChildDepth;
}

Summary: N-ary Trees Power Real Systems

We've explored the rich landscape of N-ary tree applications in production software:

Key Takeaways

•File systems are natural N-ary trees — directories contain arbitrary files/subdirectories. Size computation uses postorder; search uses preorder.
•The DOM represents web pages as N-ary trees — understanding this illuminates how browsers and JavaScript frameworks work.
•JSON and XML are hierarchical data formats that parse into trees — traversal enables querying and transformation.
•Organizational structures map to trees — enabling team size, compensation rollup, and common manager calculations.
•Game scene graphs use parent-child transforms — preorder propagation makes moving grouped objects trivial.
•Expression trees represent formulas and code — postorder evaluation computes results bottom-up.
•The pattern generalizes — any hierarchical domain can leverage N-ary tree algorithms.

Module Complete:

You've now mastered N-ary trees—from understanding why binary trees aren't always sufficient, through representation strategies and traversal adaptations, to real-world applications. This knowledge generalizes the binary tree foundations you built earlier, preparing you for advanced tree topics like tries, B-trees, and more.

Module Complete

Congratulations! You've completed the N-ary Trees & General Tree Structures module. You understand why binary constraints are sometimes limiting, how to represent and traverse N-ary trees, and where they appear in file systems, web pages, games, and compilers. This knowledge forms the foundation for advanced tree structures in databases, search systems, and beyond.

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

4 / 4

Use Cases — File Systems, Expression Trees, and Beyond

N-ary Trees in the Wild

What You Will Learn

File Systems: The Quintessential N-ary Tree

File systems are perhaps the most intuitive example of N-ary trees. Every operating system—Windows, macOS, Linux—organizes files into a hierarchical directory structure:

The root directory (C:\ on Windows, / on Unix) is the tree's root node
Directories are internal nodes that can contain any number of children
Files are leaf nodes (they have no children)

This structure admits all the operations we've studied: traversal, search, size computation, and more.

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
interface FileSystemNode {
    name: string;
    type: "file" | "directory";
    size: number;          // File size in bytes (0 for directories)
    modifiedAt: Date;
    children: FileSystemNode[];  // Empty array for files
}
 
// Example structure:
const projectDir: FileSystemNode = {
    name: "my-project",
    type: "directory",
    size: 0,
    modifiedAt: new Date("2024-01-15"),
    children: [
        {
            name: "README.md",
            type: "file",
            size: 2048,
            modifiedAt: new Date("2024-01-14"),
            children: []
        },
        {
            name: "src",
            type: "directory",
            size: 0,
            modifiedAt: new Date("2024-01-15"),
            children: [
                {
                    name: "index.ts",
                    type: "file",
                    size: 5120,
                    modifiedAt: new Date("2024-01-15"),
                    children: []
                },
                {
                    name: "utils.ts",
                    type: "file",
                    size: 3072,
                    modifiedAt: new Date("2024-01-13"),
                    children: []
                }
            ]
        },
        {
            name: "package.json",
            type: "file",
            size: 1024,
            modifiedAt: new Date("2024-01-10"),
            children: []
        }
    ]
};

Common file system operations as tree 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
67
68
69
70
71
72
73
74
75
76
77
// 1. Calculate total directory size (POSTORDER)
function getDirectorySize(node: FileSystemNode): number {
    if (node.type === "file") {
        return node.size;
    }
    
    // Directory: sum of all children's sizes
    let total = 0;
    for (const child of node.children) {
        total += getDirectorySize(child);
    }
    return total;
}
 
// 2. Find all files matching a pattern (PREORDER with filter)
function findFiles(
    node: FileSystemNode, 
    pattern: RegExp
): FileSystemNode[] {
    const results: FileSystemNode[] = [];
    
    function search(current: FileSystemNode): void {
        if (current.type === "file" && pattern.test(current.name)) {
            results.push(current);
        }
        
        for (const child of current.children) {
            search(child);
        }
    }
    
    search(node);
    return results;
}
 
// Usage: Find all TypeScript files
const tsFiles = findFiles(projectDir, /\.tsx?$/);
 
// 3. Get the path to a specific file (search with path tracking)
function findPath(
    node: FileSystemNode, 
    targetName: string,
    currentPath: string = ""
): string | null {
    const nodePath = currentPath + "/" + node.name;
    
    if (node.name === targetName) {
        return nodePath;
    }
    
    for (const child of node.children) {
        const found = findPath(child, targetName, nodePath);
        if (found !== null) return found;
    }
    
    return null;
}
 
// Usage: findPath(projectDir, "utils.ts") 
// Returns: "/my-project/src/utils.ts"
 
// 4. List directory contents at depth (LEVEL-ORDER)
function listAtDepth(node: FileSystemNode, depth: number): string[] {
    let currentLevel = [node];
    let currentDepth = 0;
    
    while (currentLevel.length > 0 && currentDepth < depth) {
        const nextLevel: FileSystemNode[] = [];
        for (const n of currentLevel) {
            nextLevel.push(...n.children);
        }
        currentLevel = nextLevel;
        currentDepth++;
    }
    
    return currentLevel.map(n => n.name);
}

Real File System Commands

Document Object Model: Web Page Structure

The DOM is the interface between JavaScript and the page content. Understanding it as an N-ary tree illuminates how DOM manipulation works.

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
<!-- HTML Source -->
<html>
  <head>
    <title>My Page</title>
    <style>/* styles */</style>
  </head>
  <body>
    <header>
      <nav>
        <a href="/">Home</a>
        <a href="/about">About</a>
      </nav>
    </header>
    <main>
      <article>
        <h1>Welcome</h1>
        <p>Content here...</p>
      </article>
    </main>
  </body>
</html>
 
<!-- 
DOM Tree Structure:
html (root)
├── head
│   ├── title ("My Page")
│   └── style
└── body
    ├── header
    │   └── nav
    │       ├── a ("Home")
    │       └── a ("About")
    └── main
        └── article
            ├── h1 ("Welcome")
            └── p ("Content here...")
-->

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
// The DOM provides N-ary tree navigation built-in:
 
// Accessing children (returns live NodeList)
const children = element.childNodes;      // All child nodes
const elements = element.children;        // Only element children
 
// Parent access
const parent = element.parentNode;
const parentElement = element.parentElement;
 
// Sibling access (like LCRS right pointer!)
const nextSib = element.nextSibling;
const prevSib = element.previousSibling;
 
// Example: Count all elements in a subtree (preorder traversal)
function countElements(root: Element): number {
    let count = 1;  // Count this element
    
    for (const child of root.children) {
        count += countElements(child);
    }
    
    return count;
}
 
// Example: Find all elements with a specific class
function findByClass(root: Element, className: string): Element[] {
    const results: Element[] = [];
    
    if (root.classList.contains(className)) {
        results.push(root);
    }
    
    for (const child of root.children) {
        results.push(...findByClass(child, className));
    }
    
    return results;
}
 
// (In practice, use querySelector/querySelectorAll which do this internally)

Key DOM operations as tree algorithms:

DOM Operation	Tree Algorithm	Traversal Type
`getElementById()`	Search tree	Preorder (early exit)
`getElementsByTagName()`	Filter + collect	Preorder
`querySelector()`	CSS selector match	Preorder
`innerHTML` get	Serialize subtree	Preorder
`remove()`	Delete subtree	Postorder (detach children first)
Render layout	Compute sizes	Postorder (children before parent)
Event bubbling	Walk to root	Follow parent pointers

Virtual DOM in React

XML and JSON: Data as Trees

XML and JSON are hierarchical data formats that naturally map to N-ary trees. Parsers convert text into tree structures, and serializers convert trees back to text.

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
{
  "company": {
    "name": "TechCorp",
    "departments": [
      {
        "name": "Engineering",
        "teams": [
          { "name": "Backend", "headcount": 15 },
          { "name": "Frontend", "headcount": 10 },
          { "name": "DevOps", "headcount": 5 }
        ]
      },
      {
        "name": "Sales",
        "teams": [
          { "name": "Enterprise", "headcount": 20 },
          { "name": "SMB", "headcount": 12 }
        ]
      }
    ]
  }
}
 
// This JSON forms a tree:
// company (root)
// ├── name: "TechCorp"
// └── departments (array → internal node)
//     ├── Engineering
//     │   ├── name: "Engineering"
//     │   └── teams (array)
//     │       ├── { Backend, 15 }
//     │       ├── { Frontend, 10 }
//     │       └── { DevOps, 5 }
//     └── Sales
//         ├── name: "Sales"
//         └── teams (array)
//             ├── { Enterprise, 20 }
//             └── { SMB, 12 }

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
// Generic JSON value type
type JsonValue = 
    | string 
    | number 
    | boolean 
    | null 
    | JsonValue[] 
    | { [key: string]: JsonValue };
 
// Traverse all nodes in a JSON structure
function traverseJson(
    value: JsonValue,
    callback: (path: string[], value: JsonValue) => void,
    path: string[] = []
): void {
    callback(path, value);
    
    if (Array.isArray(value)) {
        // Array: children are indexed elements
        value.forEach((item, index) => {
            traverseJson(item, callback, [...path, String(index)]);
        });
    } else if (value !== null && typeof value === "object") {
        // Object: children are key-value pairs
        for (const [key, child] of Object.entries(value)) {
            traverseJson(child, callback, [...path, key]);
        }
    }
    // Primitives (string, number, boolean, null) are leaves
}
 
// Usage: Find all paths to numeric values
const numericPaths: string[][] = [];
traverseJson(data, (path, value) => {
    if (typeof value === "number") {
        numericPaths.push(path);
    }
});
 
// Result: [
//   ["company", "departments", "0", "teams", "0", "headcount"],
//   ["company", "departments", "0", "teams", "1", "headcount"],
//   ...
// ]

XML processing patterns:

XML uses two main parsing approaches:

DOM parsing — Build the entire tree in memory, then traverse. Good for small-to-medium documents where you need random access.
SAX/StAX parsing — Stream through the document, firing events (start element, end element, text). Never builds full tree. Good for huge documents or when you only need specific data.

Both approaches treat XML as a tree—DOM explicitly builds it, SAX implicitly traverses it via events.

Organizational Hierarchies: People Trees

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
interface Employee {
    id: string;
    name: string;
    title: string;
    salary: number;
    hireDate: Date;
    directReports: Employee[];
}
 
// Find total compensation under a manager (POSTORDER)
function getTotalCompensation(employee: Employee): number {
    let total = employee.salary;
    
    for (const report of employee.directReports) {
        total += getTotalCompensation(report);
    }
    
    return total;
}
 
// Count team size including all nested reports (POSTORDER)
function getTeamSize(employee: Employee): number {
    let size = 1;  // Count self
    
    for (const report of employee.directReports) {
        size += getTeamSize(report);
    }
    
    return size;
}
 
// Find the management chain (root to this employee)
function getManagementChain(
    root: Employee, 
    targetId: string
): Employee[] | null {
    if (root.id === targetId) {
        return [root];
    }
    
    for (const report of root.directReports) {
        const chain = getManagementChain(report, targetId);
        if (chain !== null) {
            return [root, ...chain];  // Prepend current manager
        }
    }
    
    return null;
}
 
// Find common manager of two employees (LCA problem!)
function findCommonManager(
    root: Employee,
    id1: string,
    id2: string
): Employee | null {
    // Check if this subtree contains the target
    function contains(emp: Employee, targetId: string): boolean {
        if (emp.id === targetId) return true;
        return emp.directReports.some(r => contains(r, targetId));
    }
    
    // If both targets are in this subtree
    if (!contains(root, id1) || !contains(root, id2)) {
        return null;
    }
    
    // If root is one of the targets
    if (root.id === id1 || root.id === id2) {
        return root;
    }
    
    // Count how many children contain either target
    const containingChildren = root.directReports.filter(
        r => contains(r, id1) || contains(r, id2)
    );
    
    if (containingChildren.length === 2) {
        // Targets are in different subtrees; root is LCA
        return root;
    } else if (containingChildren.length === 1) {
        // Both targets in same subtree; recurse
        return findCommonManager(containingChildren[0], id1, id2);
    }
    
    return null;
}
 
// Get org depth (management levels)
function getOrgDepth(root: Employee): number {
    if (root.directReports.length === 0) return 0;
    
    let maxDepth = 0;
    for (const report of root.directReports) {
        maxDepth = Math.max(maxDepth, getOrgDepth(report));
    }
    
    return 1 + maxDepth;
}

HR Analytics Use Cases

Game Scene Graphs: Rendering Hierarchies

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
interface Transform {
    position: { x: number; y: number; z: number };
    rotation: { x: number; y: number; z: number };
    scale: { x: number; y: number; z: number };
}
 
interface SceneNode {
    name: string;
    localTransform: Transform;     // Relative to parent
    worldTransform?: Transform;    // Computed absolute position
    mesh?: string;                 // Reference to renderable mesh
    children: SceneNode[];
}
 
// Example: A robot arm
const robotArm: SceneNode = {
    name: "RobotArm",
    localTransform: { 
        position: { x: 0, y: 0, z: 0 },
        rotation: { x: 0, y: 0, z: 0 },
        scale: { x: 1, y: 1, z: 1 }
    },
    children: [
        {
            name: "Shoulder",
            localTransform: { 
                position: { x: 0, y: 1, z: 0 },
                rotation: { x: 0, y: 0, z: 0 },
                scale: { x: 1, y: 1, z: 1 }
            },
            mesh: "shoulder_mesh",
            children: [
                {
                    name: "Elbow",
                    localTransform: { 
                        position: { x: 0, y: 1.5, z: 0 },
                        rotation: { x: 0, y: 0, z: 0 },
                        scale: { x: 1, y: 1, z: 1 }
                    },
                    mesh: "elbow_mesh",
                    children: [
                        {
                            name: "Hand",
                            localTransform: { 
                                position: { x: 0, y: 1, z: 0 },
                                rotation: { x: 0, y: 0, z: 0 },
                                scale: { x: 1, y: 1, z: 1 }
                            },
                            mesh: "hand_mesh",
                            children: []
                        }
                    ]
                }
            ]
        }
    ]
};

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
// Update world transforms - PREORDER traversal
// Parents must be updated before children!
function updateWorldTransforms(
    node: SceneNode, 
    parentWorld: Transform
): void {
    // Compute this node's world transform
    // (simplified - real implementation uses matrix multiplication)
    node.worldTransform = combineTransforms(parentWorld, node.localTransform);
    
    // Update children with this node's world transform
    for (const child of node.children) {
        updateWorldTransforms(child, node.worldTransform);
    }
}
 
function combineTransforms(parent: Transform, local: Transform): Transform {
    return {
        position: {
            x: parent.position.x + local.position.x * parent.scale.x,
            y: parent.position.y + local.position.y * parent.scale.y,
            z: parent.position.z + local.position.z * parent.scale.z,
        },
        rotation: {
            x: parent.rotation.x + local.rotation.x,
            y: parent.rotation.y + local.rotation.y,
            z: parent.rotation.z + local.rotation.z,
        },
        scale: {
            x: parent.scale.x * local.scale.x,
            y: parent.scale.y * local.scale.y,
            z: parent.scale.z * local.scale.z,
        }
    };
}
 
// Render scene - PREORDER (could also use painters algorithm)
function render(node: SceneNode): void {
    if (node.mesh && node.worldTransform) {
        drawMesh(node.mesh, node.worldTransform);
    }
    
    for (const child of node.children) {
        render(child);
    }
}
 
function drawMesh(meshId: string, transform: Transform): void {
    console.log(`Rendering ${meshId} at position ${JSON.stringify(transform.position)}`);
    // Actual GPU rendering calls here
}

Why scene graphs use N-ary trees:

Transform inheritance — Children inherit parent transforms. Moving a car moves its wheels automatically.
Grouped manipulation — Select a character node, transform the entire character including all body parts.
Culling optimization — If a parent is outside the camera view, skip rendering all children.
Animation systems — Skeletal animation applies rotations to parent bones, children follow.
Level of detail — Replace entire subtrees with simpler versions based on distance.

Expression Trees: Parsing and Evaluation

Expression trees represent mathematical or logical expressions in tree form. While simple arithmetic uses binary trees (each operator has two operands), many real expressions are N-ary:

Function calls: max(a, b, c, d) has 4 arguments
Variable-arity operators: sum(1, 2, 3, 4, 5) could take any number
List literals: [1, 2, 3, 4]
Method chains: object.method1().method2().method3()

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
type ExprNode = 
    | { type: "number"; value: number }
    | { type: "variable"; name: string }
    | { type: "binary"; operator: "+" | "-" | "*" | "/"; left: ExprNode; right: ExprNode }
    | { type: "function"; name: string; args: ExprNode[] };  // N-ary!
 
// Example: max(x + 1, y * 2, 10)
const expr: ExprNode = {
    type: "function",
    name: "max",
    args: [
        {
            type: "binary",
            operator: "+",
            left: { type: "variable", name: "x" },
            right: { type: "number", value: 1 }
        },
        {
            type: "binary",
            operator: "*",
            left: { type: "variable", name: "y" },
            right: { type: "number", value: 2 }
        },
        { type: "number", value: 10 }
    ]
};
 
// Tree structure:
//            max (function, 3 children)
//           / |  \
//          +  *   10
//         /| /\
//        x 1 y 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
type Environment = Map<string, number>;
 
const builtinFunctions: Record<string, (...args: number[]) => number> = {
    max: (...args) => Math.max(...args),
    min: (...args) => Math.min(...args),
    sum: (...args) => args.reduce((a, b) => a + b, 0),
    avg: (...args) => args.reduce((a, b) => a + b, 0) / args.length,
};
 
function evaluate(expr: ExprNode, env: Environment): number {
    switch (expr.type) {
        case "number":
            return expr.value;
            
        case "variable":
            const val = env.get(expr.name);
            if (val === undefined) {
                throw new Error(`Undefined variable: ${expr.name}`);
            }
            return val;
            
        case "binary":
            // POSTORDER: evaluate children (operands) first
            const left = evaluate(expr.left, env);
            const right = evaluate(expr.right, env);
            switch (expr.operator) {
                case "+": return left + right;
                case "-": return left - right;
                case "*": return left * right;
                case "/": return left / right;
            }
            
        case "function":
            // POSTORDER: evaluate all arguments first
            const argValues = expr.args.map(arg => evaluate(arg, env));
            
            const fn = builtinFunctions[expr.name];
            if (!fn) {
                throw new Error(`Unknown function: ${expr.name}`);
            }
            return fn(...argValues);
    }
}
 
// Usage
const env = new Map([["x", 5], ["y", 3]]);
const result = evaluate(expr, env);
// max(5 + 1, 3 * 2, 10) = max(6, 6, 10) = 10

AST in Compilers

Additional N-ary Tree Applications

Beyond the detailed examples above, N-ary trees appear in many other contexts:

More N-ary Tree Applications
Application	Tree Structure	Key Operations
Menu Systems	Menu → Submenus → Items	Navigation, highlight tracking, keyboard traversal
Taxonomies	Kingdom → Phylum → Class → ...	Classification, nearest common ancestor
Comment Threads	Post → Replies → Nested Replies	Chronological sorting, depth limiting, collapse/expand
Decision Trees (ML)	Feature tests → outcomes	Prediction (preorder), training (postorder metrics)
Trie (Prefix Trees)	Root → characters → ...	Autocomplete, spell check, IP routing
B-Trees / B+Trees	Keys with many children	Database indexing, disk-based storage
Category Hierarchies	Top Category → Subcategories	E-commerce navigation, content organization
Undo History (branching)	State → alternative futures	Version control, document editing

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 Comment {
    id: string;
    author: string;
    text: string;
    timestamp: Date;
    replies: Comment[];  // N-ary: any number of replies
}
 
// Render comments with proper nesting (preorder)
function renderComments(comments: Comment[], depth: number = 0): void {
    for (const comment of comments) {
        const indent = "  ".repeat(depth);
        console.log(`${indent}[${comment.author}]: ${comment.text}`);
        
        // Recursively render replies
        renderComments(comment.replies, depth + 1);
    }
}
 
// Count total comments including all nested replies
function countAllComments(comments: Comment[]): number {
    let count = comments.length;
    for (const comment of comments) {
        count += countAllComments(comment.replies);
    }
    return count;
}
 
// Find deepest comment level
function maxCommentDepth(comments: Comment[]): number {
    if (comments.length === 0) return 0;
    
    let maxChildDepth = 0;
    for (const comment of comments) {
        maxChildDepth = Math.max(maxChildDepth, maxCommentDepth(comment.replies));
    }
    return 1 + maxChildDepth;
}

Summary: N-ary Trees Power Real Systems

We've explored the rich landscape of N-ary tree applications in production software:

Key Takeaways

•File systems are natural N-ary trees — directories contain arbitrary files/subdirectories. Size computation uses postorder; search uses preorder.
•The DOM represents web pages as N-ary trees — understanding this illuminates how browsers and JavaScript frameworks work.
•JSON and XML are hierarchical data formats that parse into trees — traversal enables querying and transformation.
•Organizational structures map to trees — enabling team size, compensation rollup, and common manager calculations.
•Game scene graphs use parent-child transforms — preorder propagation makes moving grouped objects trivial.
•Expression trees represent formulas and code — postorder evaluation computes results bottom-up.
•The pattern generalizes — any hierarchical domain can leverage N-ary tree algorithms.

Module Complete:

Module Complete

4 / 4