3
\$\begingroup\$

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:

enter image description here

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);
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ This code is rather confusing, and isn't an up-to-scratch implementation of an IEnumerator<T> consumer. What advantage does this have over using a foreach loop or LINQ's Max? This code also introduces different null checking behaviour (nodeEnum.Current?.) which may obscure bugs. Without CTO (which is in no way guaranteed in C#, and can't be performed without an understanding that Max is associative), this will have significantly worse memory characteristics than a simple DFS. \$\endgroup\$ – VisualMelon May 6 at 10:05
  • \$\begingroup\$ @VisualMelon: On matters religious: Criticism accepted... 1. It is confusing 2. Null-checking syntax is inconsistent. I should have spent more time on writing "inspection-worthy code". I don't get your "up-to-scratch consumption" chirp... and would be keen to see it improved (by all means with LINQ or foreach, but preserving the point I was trying to make about the - arguably - more intuitive depth-first approach please). On matters empirical: I'd need to see something more substantial to support an opinion about "memory characteristics". \$\endgroup\$ – AlanK May 6 at 10:24
  • \$\begingroup\$ It's fine to provide an alternative suggestion, but it needs to be clear why you think it would be better option in some way (and ideally identify any deficiencies, which can be hard to see in questions like this because there are no real requirements). You ought to be disposing the IEnumerator<T> (e.g. in a finally block); I'm afraid I can't find a sensible reference this minute. I suggest we continue this discussion in chat so that we don't flood the comment section. \$\endgroup\$ – VisualMelon May 6 at 10:31
  • \$\begingroup\$ @VisualMelon: Keeping it off chat for the moment because the observation about disposing the enumerator is vital. Thanks. I've updated my code. As for motivating the suggestion, I think I did that. \$\endgroup\$ – AlanK May 6 at 10:52
  • \$\begingroup\$ Fair enough. I wrote some comments concerning the memory usage in chat if you wanted to see those. \$\endgroup\$ – VisualMelon May 6 at 11:22
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.