LeetCode: N-ary Tree Level Order Traversal https://leetcode.com/problems/n-ary-tree-level-order-traversal/

Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example, given a 3-ary tree:



We should return its level order traversal:

[
     [1],
     [3,2,4],
     [5,6]
]

Note:

The depth of the tree is at most 1000.
The total number of nodes is at most 5000.

Please comment about space and time complexity.
Thanks.

using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace GraphsQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/problems/n-ary-tree-level-order-traversal/
    /// &lt;/summary&gt;

    [TestClass]
    public class N_aryTreeLevelOrderTraversal
    {
        [TestMethod]
        public void N_aryTreeLevelOrderTraversalTest()
        {
            List&lt;Node&gt; node3 = new List&lt;Node&gt;();
            node3.Add(new Node(5, null));
            node3.Add(new Node(6, null));

            List&lt;Node&gt; node1 = new List&lt;Node&gt;();
            node1.Add(new Node(3, node3));
            node1.Add(new Node(2, null));
            node1.Add(new Node(4, null));

            Node root = new Node(1, node1);
            var result = LevelOrder(root);
            IList&lt;IList&lt;int&gt;&gt; expected = new List&lt;IList&lt;int&gt;&gt;();
            expected.Add(new List&lt;int&gt;{1});
            expected.Add(new List&lt;int&gt;{3,2,4});
            expected.Add(new List&lt;int&gt;{5,6});

            for (int i = 0; i &lt; 3; i++)
            {
                CollectionAssert.AreEqual(expected[i].ToArray(), result[i].ToArray());
            }

        }
        public IList&lt;IList&lt;int&gt;&gt; LevelOrder(Node root)
        {
            IList&lt;IList&lt;int&gt;&gt; result = new List&lt;IList&lt;int&gt;&gt;();
            Queue&lt;Node&gt; Q = new Queue&lt;Node&gt;();
            if (root == null)
            {
                return result;
            }

            Q.Enqueue(root);

            while (Q.Count &gt; 0)
            {
                List&lt;int&gt; currentLevel = new List&lt;int&gt;();
                int qSize = Q.Count;
                for (int i = 0; i &lt; qSize; i++)
                {
                    var curr = Q.Dequeue();
                    currentLevel.Add(curr.val);
                    if (curr.children != null)
                    {
                        foreach (var child in curr.children)
                        {
                            Q.Enqueue(child);
                        }
                    }
                }
                result.Add(currentLevel);
            }
            return result;
        }
    }
}
Time and space complexity are just the number of nodes in the graph. You can't do better than this with the API given. If the API were open to negotiation, I'd consider IEnumerable&lt;IReadonlyList&lt;int&gt;&gt;, which would permit better memory characteristics for some trees (e.g. if the level-width stays reasonably constant rather than, say, growing exponentially). There is also no need for this to be an instance method.



I don't like this:



if (root == null)
{
    return result;
}


No-where in the spec is it said that a null input should produce a null output, and this is a design decision which needs to be documented. Without something saying that null should map to null, I'd much prefer an ArgumentNullException which doesn't obscure any assumptions. If this behaviour is wrong, then you'll know the moment you try to use it. If returning null is wrong, it might take you a while to find out where your code messed up. Either behaviour warrents inline documentation. I'd also prefer these sorts of checks were performed straight-away, so that they can't be lost in the other clutter, and in this case avoid unnecessarily allocations.

Similarly, is it specified that Node.children can be null, and that this is supported? If not, then I'd be inclined to remove the check, as it will simplify the code and cause it to blow up if this assumption is violated, forcing the consumer to address the null rather than hoping the behaviour is as expected. (Ideally any constraint would be enforced by the Node class, and I appreciate that isn't yours to change).



Q isn't a great variable name: it describes what the thing is, which can be confused with its purpose; and because it is capitalised, it feels like a member variable.



It would be nicer if the test methods were separated from the functionality. Currently, anyone trying to find aryTreeLevelOrderTraversal.LevelOrder will be confronted with N_aryTreeLevelOrderTraversalTest in their intellisense



Personally I don't like this sort of 'staged' consumption of a queue; it just feels fiddily. In this case you can avoid it completely (and save memory) by enumerating over the previous level when you construct the next. This can make the code more-compact, and harder to break (e.g. someone might 'helpfully' inline qSize thinking it's clearer only to break the code completely) with fewer variables whereof to keep track. With a bit of LINQ, we can write (untested):

List&lt;int&gt; level = new List&lt;int&gt; { root };
while (level.Count &gt; 0)
{
    result.Add(level);
    level = level.Where(n =&gt; n.Children != null).SelectMany(n =&gt; n.children).ToList();
}


There is virtually nothing to go wrong here apart from getting those 2 lines inside the loop the wrong way round. You don't need anything more complex unless performance is a real concern, or you want a lazy implementation, in which case you need to be careful you don't yield state you are about to access:

List&lt;int&gt; level = new List&lt;int&gt; { root };
while (level.Count &gt; 0)
{
    var previous = level;
    level = previous.Where(n =&gt; n.Children != null).SelectMany(n =&gt; n.children).ToList();
    yield return previous;
}