# LeetCode: N-ary Tree Level Order Traversal

Posted on

Problem

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.

Thanks.

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

namespace GraphsQuestions
{
/// <summary>
/// https://leetcode.com/problems/n-ary-tree-level-order-traversal/
/// </summary>

[TestClass]
public class N_aryTreeLevelOrderTraversal
{
[TestMethod]
public void N_aryTreeLevelOrderTraversalTest()
{
List<Node> node3 = new List<Node>();

List<Node> node1 = new List<Node>();

Node root = new Node(1, node1);
var result = LevelOrder(root);
IList<IList<int>> expected = new List<IList<int>>();

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

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

Q.Enqueue(root);

while (Q.Count > 0)
{
List<int> currentLevel = new List<int>();
int qSize = Q.Count;
for (int i = 0; i < qSize; i++)
{
var curr = Q.Dequeue();
if (curr.children != null)
{
foreach (var child in curr.children)
{
Q.Enqueue(child);
}
}
}
}
return result;
}
}
}
``````

Solution

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<IReadonlyList<int>>`, 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<int> level = new List<int> { root };
while (level.Count > 0)
{
level = level.Where(n => n.Children != null).SelectMany(n => 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<int> level = new List<int> { root };
while (level.Count > 0)
{
var previous = level;
level = previous.Where(n => n.Children != null).SelectMany(n => n.children).ToList();
yield return previous;
}
``````

The algorithm can be rewritten to use Linq instead of a Queue.

``````public IList<IList<int>> LevelOrder(Node root)
{
IList<IList<int>> result = new List<IList<int>>();
Queue<Node> Q = new Queue<Node>();
..
``````

This increases readability. (At the cost of performance?) I use `IEnumerable` when mutation of the list is not required and `IList` otherwise.

``````public static IEnumerable<IEnumerable<int>> LevelOrder(Node root)
{
}

{
}
}
``````

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. – VisualMelon

I have asserted the children always be set. No need for boiler-plate `null` checks, at the expensive of slight object creation overhead.

``````public class Node
{
public int val;
public IList<Node> children;

public Node() {
}

public Node(int val, IList<Node> children) {
this.val = val;
this.children = children ?? new List<Node>();
}
}
``````

test entrypoint (I used a console app and debugged the results, but you are better of writing a unit test.)

``````public static void Main()
{
var node3 = new List<Node>();

var node1 = new List<Node>();