N Ary Tree Level Order Traversal

                                            
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution(object):
    def levelOrder(self, root):
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                level.append(node.val)
                queue.extend(node.children)
            result.append(level)
        
        return result

                                            
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 */

var levelOrder = function(root) {
    if(!root) return [];
    
    let result = [];
    let queue = [root];
    
    while(queue.length > 0) {
        let size = queue.length;
        let currentLevel = [];
        
        for(let i = 0; i < size; i++) {
            let node = queue.shift();
            currentLevel.push(node.val);
            if(node.children) {
                queue.push(...node.children);
            }
        }
        
        result.push(currentLevel);
    }
    
    return result;
};

                                            
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     children: Node[]
 *     constructor(val?: number) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.children = []
 *     }
 * }
 */
function levelOrder(root: Node | null): number[][] {
    if (!root) return [];

    const result: number[][] = [];
    const queue: Node[] = [root];

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

        for (let i = 0; i < levelSize; i++) {
            const current: Node = queue.shift() as Node;
            currentLevel.push(current.val);
            current.children.forEach(child => queue.push(child));
        }

        result.push(currentLevel);
    }

    return result;
}

                                            
/**
 * Definition for a Node.
 * class Node {
 *     public $val = null;
 *     public $children = [];
 * }
 */
class Solution {

    /**
     * @param Node $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        if ($root === null) return [];
        $result = [];
        $queue = [$root];
        
        while (!empty($queue)) {
            $level = [];
            $size = count($queue);
            for ($i = 0; $i < $size; $i++) {
                $node = array_shift($queue);
                $level[] = $node->val;
                foreach ($node->children as $child) {
                    array_push($queue, $child);
                }
            }
            $result[] = $level;
        }
        
        return $result;
    }
}

                                            
/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var children: [Node]
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.children = []
 *     }
 * }
 */

class Solution {
    func levelOrder(_ root: Node?) -> [[Int]] {
        guard let root = root else { return [] }
        
        var result = [[Int]]()
        var queue = [Node]()
        queue.append(root)
        
        while !queue.isEmpty {
            var levelValues = [Int]()
            let levelSize = queue.count
            
            for _ in 0..<levelSize {
                let node = queue.removeFirst()
                levelValues.append(node.val)
                queue.append(contentsOf: node.children)
            }
            
            result.append(levelValues)
        }
        
        return result
    }
}

                                            
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func levelOrder(root *Node) [][]int {
    result := [][]int{}
    if root == nil {
        return result
    }

    queue := []*Node{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        levelValues := []int{}
        
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            levelValues = append(levelValues, node.Val)
            for _, child := range node.Children {
                queue = append(queue, child)
            }
        }
        
        result = append(result, levelValues)
    }
    
    return result
}

                                            
# Definition for a Node.
# class Node
#     attr_accessor :val, :children
#     def initialize(val)
#         @val = val
#         @children = []
#     end
# end

# @param {Node} root
# @return {Integer[][]}
def level_order(root)
    return [] if root.nil?
    
    result = []
    queue = [root]
    
    until queue.empty?
        current_level = []
        next_level = []
        
        queue.each do |node|
            current_level << node.val
            next_level += node.children if node.children
        end
        
        result << current_level
        queue = next_level
    end
    
    result
end

                                            
/**
 * Definition for a Node.
 * class Node(var _value: Int) {
 *   var value: Int = _value
 *   var children: List[Node] = List()
 * }
 */

object Solution {
    def levelOrder(root: Node): List[List[Int]] = {
        import scala.collection.mutable.Queue
        
        val result = scala.collection.mutable.ListBuffer[List[Int]]()
        
        if (root == null) return result.toList

        val q = Queue[Node]()
        q.enqueue(root)

        while (q.nonEmpty) {
            val levelSize = q.size
            val levelNodes = scala.collection.mutable.ListBuffer[Int]()

            for (_ <- 0 until levelSize) {
                val node = q.dequeue()
                levelNodes += node.value
                for(child <- node.children) {
                    if(child != null) q.enqueue(child)
                }
            }

            result += levelNodes.toList
        }

        result.toList
    }
}

To solve this coding challenge, we need to perform a level order traversal on an n-ary tree and return the values of the nodes in a structured manner, grouped by their levels. The n-ary tree is given, where each node has a value and a list of children.

Explanation

A level order traversal, also known as breadth-first traversal, processes all nodes at the present level before moving on to nodes at the next level. To manage this, we'll employ a breadth-first search (BFS) strategy using a queue data structure. Here's a detailed step-by-step approach:

Check for Empty Tree: First, we need to handle the edge case where the tree might be empty. If the input
root

is
None

, our result should be an empty list.
Initialize Data Structures: We initialize:

A
result

list to store the nodes' values level by level.
A
queue

initialized with the root node to facilitate the BFS traversal.

BFS Traversal: We continuously process nodes level by level. For each level:

We initialize an empty
level

list to keep track of the current level's nodes.
For each node in the current level (i.e., size of the
queue

at the start of the level), we:

Pop the node from the front of the queue.
Append the node's value to the
level

list.
Add all of the node's children to the queue for processing in subsequent iterations.

Store Results: After processing all nodes at a level, we append the
level

list to the
result

list.
Return Results: Once the BFS traversal is complete, we return the
result

list containing the nodes' values grouped by their levels.

Detailed Steps in Pseudocode

Initial Check and Setup

If
root

is
None

, return an empty list.
Initialize
result

as an empty list to store the final level order values.
Initialize
queue

with the root node.

Pseudocode:

                                            
# Step 1: Check if the tree is empty
if root is None:
return []

# Step 2: Initialize result to store final level order
result = []

# Step 3: Initialize queue with the root node
queue = [root]

BFS Traversal

While there are nodes in the queue:

Initialize
level

as an empty list to store the current level's node values.
Loop through each node in the current level (using the current size of the
queue

):

Remove the node from the front of the
queue

.
Append the node’s value to the
level

list.
Add the node's children to the
queue

.

Append the
level

list to the
result

.

Pseudocode:

                                            
# Step 4: BFS traversal to process each level
while queue is not empty:
# Initialize an empty list for the current level
level = []

# Process nodes at the current level
for _ in range(len(queue)):
# Remove the front node from the queue
node = queue.pop(0)

# Add the node’s value to the current level list
level.append(node.val)

# Add the node's children to the queue for the next level
queue.extend(node.children)

# Append the current level's values to the result
result.append(level)

Return the Result

Return the
result

list containing nodes' values level by level.

Pseudocode:

                                            
# Step 5: Return the final level order traversal result
return result

By following these steps, we effectively perform a level order traversal on an n-ary tree and correctly group the nodes' values by their respective levels. This method ensures that our solution is both efficient and easy to understand.