N-ary Tree

An N-ary Tree is a tree data structure where each node can have up to N children. This is a generalization of a binary tree where each node can have more than two children. N-ary trees are useful in scenarios where a hierarchical structure is required, but nodes can have more than two children.

Properties of N-ary Trees

• Nodes: Each node in the tree has a value and a list of child nodes.
• Root Node: The topmost node in the tree, with no parent.
• Leaf Nodes: Nodes that do not have any children.
• Height: The length of the longest path from the root to a leaf node.

Basic Operations

1. Insertion: Adding a new node to the tree.
2. Deletion: Removing a node from the tree.
3. Traversal: Visiting all nodes in a specific order (e.g., pre-order, post-order).

Example Structure

An N-ary tree can be represented as:

class Node {

  constructor(val, children = []) {
    this.val = val;
    this.children = children;
  }

  // Add a child node
  addChild(child) {
    if (child instanceof Node) {
      this.children.push(child);
    } else {
      throw new Error("Invalid child node");
    }
  }

  // Remove a child node by value
  removeChild(childVal) {
    const index = this.children.findIndex(child => child.val === childVal);
    if (index !== -1) {
      this.children.splice(index, 1);
    } else {
      throw new Error("Child node not found");
    }
  }

  // Find a node by value using DFS
  findNode(val) {
    if (this.val === val) return this;

    for (const child of this.children) {
      const result = child.findNode(val);
      if (result) return result;
    }

    return null;
  }

  // Pre-order DFS Traversal
  dfsPreOrder(result = []) {
    result.push(this.val);
    for (const child of this.children) {
      child.dfsPreOrder(result);
    }
    return result;
  }

  // Post-order DFS Traversal
  dfsPostOrder(result = []) {
    for (const child of this.children) {
      child.dfsPostOrder(result);
    }
    result.push(this.val);
    return result;
  }

  // In-order Traversal (customized for N-ary trees)
  dfsInOrder(result = []) {
    const half = Math.floor(this.children.length / 2);

    for (let i = 0; i < half; i++) {
      this.children[i].dfsInOrder(result);
    }

    result.push(this.val);

    for (let i = half; i < this.children.length; i++) {
      this.children[i].dfsInOrder(result);
    }

    return result;
  }

  bfs = (root) => {
    const queue = [root]
    const result = []

    while (queue.length) {
      const current = queue.shift()
      result.push(current.val);
      for (const child of current.children) {
        queue.push(child)
      }
    }
    return result
  }

  // Level-order BFS Traversal
  static bfsLevelOrder(root) {
    const result = [];
    if (!root) return result;

    const queue = [root];

    while (queue.length > 0) {
      const levelSize = queue.length;
      const currentLevel = [];

      for (let i = 0; i < levelSize; i++) {
        const node = queue.shift();
        currentLevel.push(node.val);

        for (const child of node.children) {
          queue.push(child);
        }
      }
      result.push(currentLevel);
    }
    return result;
  }

  // Maximum Depth of the N-ary Tree
  maxDepth() {
    if (this.children.length === 0) return 1;

    let depth = 0;
    for (const child of this.children) {
      depth = Math.max(depth, child.maxDepth());
    }

    return depth + 1; // Add 1 to account for the current node
  }
}

// Create a sample N-ary tree
const root = new Node(1);
const child1 = new Node(3);
const child2 = new Node(2);
const child3 = new Node(4);

root.addChild(child1);
root.addChild(child2);
root.addChild(child3);

const grandchild1 = new Node(5);
const grandchild2 = new Node(6);

child1.addChild(grandchild1);
child1.addChild(grandchild2);


/* 
        1
       /|\
      / | \
     3  2  4
    / \
   5   6
*/


// Perform traversals
console.log('DFS Pre-order:', root.dfsPreOrder([])); // Output: [1, 3, 5, 6, 2, 4]
console.log('DFS Post-order:', root.dfsPostOrder([])); // Output: [5, 6, 3, 2, 4, 1]
console.log('DFS In-order:', root.dfsInOrder([])); // Output: [5, 6, 3, 1, 2, 4]
console.log('BFS', root.bfs(root)); //[ 1, 3, 2, 4, 5, 6 ]
console.log('BFS Level-order:', Node.bfsLevelOrder(root)); // Output: [[1], [3, 2, 4], [5, 6]]
console.log('Maximum Depth of the Tree:', root.maxDepth()); // Output: 3