LeetCode: N-ary Tree Level Order Traversal

Question

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
{
    /// <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>();
            node3.Add(new Node(5, null));
            node3.Add(new Node(6, null));

            List<Node> node1 = new List<Node>();
            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<IList<int>> expected = new List<IList<int>>();
            expected.Add(new List<int>{1});
            expected.Add(new List<int>{3,2,4});
            expected.Add(new List<int>{5,6});

            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();
                    currentLevel.Add(curr.val);
                    if (curr.children != null)
                    {
                        foreach (var child in curr.children)
                        {
                            Q.Enqueue(child);
                        }
                    }
                }
                result.Add(currentLevel);
            }
            return result;
        }
    }
}

Answer 1

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)
{
    result.Add(level);
    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;
}

Answer 2

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) 
{
    var valuesByBreadth = new List<IEnumerable<int>>();
    LevelOrder(new[] { root }, valuesByBreadth);
    return valuesByBreadth;
}

private static void LevelOrder(IEnumerable<Node> breadth, IList<IEnumerable<int>> valuesByBreadth) 
{
    if (breadth.Any()) {
        valuesByBreadth.Add(breadth.Select(x => x.val).ToList());
        LevelOrder(breadth.SelectMany(x => x.children), valuesByBreadth);
    }
}

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>();
        node3.Add(new Node(5, null));
        node3.Add(new Node(6, null));

        var node1 = new List<Node>();
        node1.Add(new Node(3, node3));
        node1.Add(new Node(2, null));
        node1.Add(new Node(4, null));

        var root = new Node(1, node1);
        var result = LevelOrder(root);

        Console.ReadKey();
    }