LeetCode: maximum-depth-of-n-ary-tree

Question

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<Node> children;

        public Node()
        {
        }

        public Node(int _val, IList<Node> _children)
        {
            val = _val;
            children = _children;
        }
    }

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

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

            int maxDepth = 0;
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                maxDepth++;
                var queueSize = queue.Count;
                for (int i = 0; i < 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<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);
            int result = MaxDepth(root);
            Assert.AreEqual(3, result);
        }
    }
}

Answer 1

Your solution seems pretty optimal - for breadth-first traversal (see below)

1. MaxDepth() could/should be static. The containing class too.
2. 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<Node> 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<Node> { root }.GetEnumerator())
  depth2 = MaximumDepthOfN_aryTree.MaxDepth2(nodeEnum);

Answer 2

It looks optimized to me, but you can add a check for maxDepth >= 1000 and break the while loop if true.

Answer 3

A recursive approach that takes into account the threshold of max depth 1000. The threshold of 5000 nodes is ambigious, because what behavior do you expect when there are more nodes?

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Globalization;
using System.Text.RegularExpressions;

public class Program
{
    public static void Main()
    {
        var node5 = new Node();
        var node6 = new Node();
        var node3 = new Node(0, new List<Node> { node5, node6 });
        var node2 = new Node();
        var node4 = new Node();
        var node1 = new Node(0, new List<Node> { node3, node2, node4 });

        Console.WriteLine("Max Depth = " + MaximumDepthOfN_aryTree.MaxDepth(node1, 1000, 1));

        Console.ReadKey();
    }

    public class MaximumDepthOfN_aryTree
    {
        public static int MaxDepth(Node root, int maxDepthThreshold, int depth) 
        {
            if (root.children == null || !root.children.Any()) {
                return depth;
            }

            if (depth == maxDepthThreshold) {
                return depth;
            }

            return root.children.Max(x => MaxDepth(x, maxDepthThreshold, depth++));
        }
    }

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

        public Node() {
        }

        public Node(int _val, IList<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}