Leetcode 559. Maximum Depth of N-ary Tree

Problem Explanation:

Given a N-ary tree, we need to find the maximum depth of this tree and return it. The maximum depth of a tree is determined by the number of nodes along the longest path from the root node to the farthest leaf node.

Consider an example where we have a 3-ary tree:

1
2
3      1 
4     /|\ 
5    2 3 4 
6   

In this case, the maximum depth is 2.

Approach:

This problem can be solved by Depth-first Search (DFS). Starting from root, we traverse each child and keep track of the maximum depth. We increment the depth at each level as we go down the tree.

Let's consider the above example again and try to walk through each step of the solution:

Step 1: We start with root node 1, and traverse its children. We find three children: 2, 3, and 4.

Step 2: For each child, we traverse its children. In this case, none of the children (2, 3, 4) have any children.

Step 3: We increment the depth at each level. The depth at root level is 1, and it increases by 1 as we go down to the next level. Therefore, the maximum depth is 2.

Now, let's see the solutions in different programming languages:

Python:

1
2python
3class Solution:
4    def maxDepth(self, root):
5        if root is None:
6            return 0
7        elif root.children == []:
8            return 1
9        else:
10            return max(self.maxDepth(child) for child in root.children) + 1

Java:

1
2java
3class Solution {
4    public int maxDepth(Node root) {
5        if (root == null)
6            return 0;
7        else {
8            int maxDepth = 0;
9            for (Node child : root.children)
10                maxDepth = Math.max(maxDepth, maxDepth(child));
11            return maxDepth + 1;
12        }
13    }
14}

JavaScript:

1
2javascript
3var maxDepth = function(root) {
4    if (!root) {
5        return 0;
6    }
7    let maxDepth = 0;
8    for (let child of root.children) {
9        maxDepth = Math.max(maxDepth, maxDepth(child));
10    }
11    return maxDepth + 1;
12};

C++:

1
2c++
3class Solution {
4public:
5    int maxDepth(Node* root) {
6        if (!root) return 0;
7        int maxDepth = 0;
8        for (Node* child : root->children)
9            maxDepth = max(maxDepth, maxDepth(child));
10        return maxDepth + 1;
11    }
12};

C#:

1
2csharp
3public class Solution {
4    public int MaxDepth(Node root) {
5        if (root == null) return 0;
6        int maxDepth = 0;
7        foreach (Node child in root.children)
8            maxDepth = Math.Max(maxDepth, MaxDepth(child));
9        return maxDepth + 1;
10    }
11}

In all these solutions, we use a DFS approach to traverse through the tree and keep updating the maximum depth.Groovy:

1
2groovy
3class Solution {
4   int maxDepth(Node root){
5       if(root == null) return 0
6       return root.children.stream().mapToInt{child -> maxDepth(child)}.max().orElse(0) + 1
7   }
8}

Ruby:

1
2ruby
3class Solution
4  def max_depth(root)
5    return 0 if root.nil?
6    return 1 if root.children.empty?
7    root.children.map { |child| max_depth(child) }.max + 1
8  end
9end

PHP:

1
2php
3class Solution {
4
5    function maxDepth($root) {
6        if($root==null) return 0;
7        $maxD=0;
8        foreach($root->children as $child) {
9            $maxD=max($maxD, $this->maxDepth($child));
10        }
11        return $maxD+1;
12    }
13}

In Groovy, we use stream API for working with collections. The mapToInt function transforms the children into their depths, and then max function finds the maximum value - or returns 0, if the stream was empty. Finally we add 1 to the result.

Ruby version uses the map method from the Enumerable module to apply maximum depth calculation to each child of a node. The result array of depths is then reduced to its maximum value using the max method, yielding the maximum depth of the tree.

In the PHP solution, we iterate over the children of each node with a foreach loop, recursively finding the maximum depth of each child and selecting the maximum of these values. We then add 1 to the result to include the current node in the count. The ternary operator (?:) is used here to return 0 when root is null.

Please note that in these implementations, the children of a node are assumed to be stored in a collection (like an array or a list), and depth of a tree with no nodes is considered to be 0. The base of the recursion is a tree with no root (null root), for which the depth is 0.

Thus, we see that the approach to solve this problem using depth-first search (DFS) is pretty consistent across all languages. The variations are mostly due to the specific syntax and APIs of each language.