LeetCode: maximum-depth-of-n-ary-tree https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:



We should return its max depth, which is 3.

Note:

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

Here is my code, and also 1 test as an example 
Please comment about space and time complexity, I also made a recursive answer but I tend to think about BFS in an iterative way while using queue, and DFS in recursive way, although you can use a stack for it as well.
so I a real interview I would probably go with BFS with a queue.

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

namespace TreeQuestions
{
    // Definition for a Node.
    public class Node
    {
        public int val;
        public IList&lt;Node&gt; children;

        public Node()
        {
        }

        public Node(int _val, IList&lt;Node&gt; _children)
        {
            val = _val;
            children = _children;
        }
    }

    /// &lt;summary&gt;
    /// https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
    /// &lt;/summary&gt;
    [TestClass]
    public class MaximumDepthOfN_aryTree
    {
        public int MaxDepth(Node root)
        {

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

            int maxDepth = 0;
            Queue&lt;Node&gt; queue = new Queue&lt;Node&gt;();
            queue.Enqueue(root);

            while (queue.Count &gt; 0)
            {
                maxDepth++;
                var queueSize = queue.Count;
                for (int i = 0; i &lt; queueSize; i++)
                {

                    var current = queue.Dequeue();
                    if (current.children != null)
                    {
                        foreach (var child in current.children)
                        {
                            queue.Enqueue(child);
                        }
                    }
                }
            }

            return maxDepth;
        }


        [TestMethod]
        public void MaximumDepthOfN_aryTreeTest()
        {
            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);
            int result = MaxDepth(root);
            Assert.AreEqual(3, result);
        }
    }
}
Your solution seems pretty optimal - for breadth-first traversal (see below)


MaxDepth() could/should be static.  The containing class too.
The LeetCode question does not require breadth-first traversal.
Depth first would not require an(y) additional data structure (no queue, but would implicitly use the stack) 
which might be optimised away by tail-recursion (if C# is smart enough).


The following is therefore not criticism but a suggested alternative.
- I would not expect (much of) a performance difference
- Space-advantage, if significant (due to tail-recursion optimisation, compiler-and/or run-time environment dependent) would have to be measured
- So the main consideration in (not) choosing depth-first traversal would be a (probably) religious argument about brevity/readability of code

public static int MaxDepth2(IEnumerator&lt;Node&gt; nodeEnum = null, int depth = 0)
{
  //  No current node
  if (nodeEnum == null || !nodeEnum.MoveNext()) return depth;

  //  The greater of current and maximum of siblings
  using (var nodeEnumInner = nodeEnum.Current?.children?.GetEnumerator())
    return Math.Max(MaxDepth2(nodeEnumInner, depth + 1), MaxDepth2(nodeEnum, depth));
}

:
:
using (var nodeEnum = new List&lt;Node&gt; { root }.GetEnumerator())
  depth2 = MaximumDepthOfN_aryTree.MaxDepth2(nodeEnum);