[LeetCode] N-ary Tree Level Order Traversal

Problem: Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example:

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

Approach: Like in case of binary tree's level order traversal, we will use queue here. The approach is same.

Implementation in C#:

    public IList<IList<int>> LevelOrder(Node root) 

    {

        List<IList<int>> result = new List<IList<int>>();

        if (root == null)

        {

            return result;

        }

        Queue<Node> queue = new Queue<Node>();

        queue.Enqueue(root);

        while(queue.Count > 0)

        {

            List<int> currRow = new List<int>();

            int size = queue.Count;

            for (int i = 0; i < size; ++i)

            {

                var node = queue.Dequeue();

                currRow.Add(node.val);

                foreach(var child in node.children)

                {

                    queue.Enqueue(child);

                }

            }

            result.Add(currRow);

        }

        return result;

    }

Complexity: O(n)