N-ary Tree

An N-ary tree is a tree data structure where each node can have up to N children. Unlike binary trees which have at most two children per node, N-ary trees can have any number of children. This structure is useful for representing hierarchical data with multiple branches at each level.

Key Characteristics

• Each node can have 0 to N children
• Root node is at level 0
• Children of a node are at the same level
• Leaves are nodes with no children

Common Use Cases

1. File Systems: Representing directories and subdirectories
2. Organization Charts: Hierarchical company structures
3. Family Trees: Genealogical data
4. XML/HTML Parsing: Tree structures in markup languages
5. Trie Data Structures: Prefix trees used in autocomplete features

Tree Node Representation

interface TreeNode {
  val: number;
  children: TreeNode[];
}

// Example of creating an N-ary tree node
const node = {
  val: 1,
  children: [
    { val: 2, children: [] },
    { val: 3, children: [] },
    { val: 4, children: [] }
  ]
};

Traversal Algorithms

Level Order Traversal

function levelOrder(root: TreeNode | null): number[] {
  if (!root) return [];
  
  const result: number[] = [];
  const queue: TreeNode[] = [root];
  
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.val);
    
    // Add all children to queue
    for (const child of node.children) {
      queue.push(child);
    }
  }
  
  return result;
}

Depth-First Search (Preorder)

function preorder(root: TreeNode | null): number[] {
  const result: number[] = [];
  
  function dfs(node: TreeNode | null) {
    if (!node) return;
    
    result.push(node.val);
    
    // Visit all children recursively
    for (const child of node.children) {
      dfs(child);
    }
  }
  
  dfs(root);
  return result;
}

Common Operations

Find Maximum Depth

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  
  let maxDepth = 0;
  
  function dfs(node: TreeNode, depth: number) {
    maxDepth = Math.max(maxDepth, depth);
    
    for (const child of node.children) {
      dfs(child, depth + 1);
    }
  }
  
  dfs(root, 1);
  return maxDepth;
}

Serialize and Deserialize

// Serialization format: [val, [children]]
function serialize(root: TreeNode | null): string {
  if (!root) return 'null';
  
  const children = root.children.map(child => serialize(child));
  return `${root.val},${children.join('|')}`;
}

function deserialize(data: string): TreeNode | null {
  if (data === 'null') return null;
  
  const parts = data.split(',');
  const rootVal = parseInt(parts[0]);
  
  const children: TreeNode[] = [];
  let i = 1;
  
  // Parse children
  while (i < parts.length) {
    const childData = parts[i];
    if (childData === '') break;
    
    const child = deserialize(childData);
    if (child) children.push(child);
    i++;
  }
  
  return {
    val: rootVal,
    children
  };
}

Time and Space Complexity Analysis

| Operation | Time Complexity | Space Complexity |

|-----------|----------------|------------------|

| Traversal (BFS) | O(N) | O(W) where W is max width |

| Traversal (DFS) | O(N) | O(H) where H is max height |

| Find Maximum Depth | O(N) | O(H) |

| Serialization | O(N) | O(N) |

| Deserialization | O(N) | O(N) |

Common Mistakes to Avoid

1. Incorrect Assumption About Children: Not all nodes in an N-ary tree will have the same number of children
2. Missing Base Case: For recursive algorithms, forgetting to handle null or empty root nodes
3. Incorrect Traversal Order: Mixing up preorder and postorder traversals
4. Memory Leaks: Not properly cleaning up references in complex tree structures
5. Not Handling Empty Trees: Assuming the root node always exists

Real-World Applications

1. File System Navigation: Representing directory structures with multiple subdirectories
2. Social Media Hierarchies: Organizing comments and replies in threaded discussions
3. Game Trees: Representing game states and possible moves in AI decision trees
4. Document Outlines: Organizing hierarchical content in word processors
5. Database Hierarchies: Representing parent-child relationships in hierarchical databases

Practice Problems

1. Maximum Depth of N-ary Tree
2. N-ary Tree Level Order Traversal
3. Serialize and Deserialize N-ary Tree
4. N-ary Tree Postorder Traversal
5. Find the Maximum Value in an N-ary Tree

Best Practices

1. Consistent Node Structure: Always define nodes with the same interface for predictability
2. Handle Edge Cases: Always consider empty trees and single-node trees
3. Use Iterative Approaches When Possible: To avoid stack overflow in very deep trees
4. Implement Proper Memory Management: Clean up references to prevent memory leaks in long-running applications
5. Validate Input Data: Ensure that tree structures are properly formed before processing