Maximum Depth Of N Ary Tree - Leetcode Solution

Problem: Given an n-ary tree, find its maximum depth.

Solution:

The solution to this problem can be approached using a recursive method. We can start with the root node and traverse down to all its child nodes, then recursively calculate the maximum depth of each child node.

Algorithm:

1. Create a function maxDepth that takes the root node as its parameter.
2. Initialize a variable depth with a value of 1.
3. If the root node is None, return 0.
4. Loop through all its child nodes, and recursively call maxDepth function on each child node with depth incremented by 1.
5. For each recursive call, compute the maximum depth and keep track of the maximum depth found so far.
6. Return the maximum depth.

Pseudo-code:

def maxDepth(root):
    if root is None:
        return 0
    else:
        depth = 1
        for child in root.children:
            depth = max(depth, maxDepth(child) + 1)
        return depth

Time Complexity: O(n) where n is the total number of nodes in the n-ary tree.

Space Complexity: O(h) where h is the height of the n-ary tree.

Explanation:

In the maxDepth function, we initialize the depth variable with a value of 1 because the root node has a depth of 1. Then we check if the root node is None or not. If the root node is None, we return 0 because there are no nodes in the tree.

After that, we loop through all the child nodes of the root node, and for each child node, we calculate the depth by calling the maxDepth function recursively with the child node as the root node and the depth incremented by 1.

We take the maximum depth found for all child nodes and add 1 to it to get the maximum depth of the root node.

Finally, we return the maximum depth of the n-ary tree.

Overall, this method follows a depth-first search approach, traversing all nodes in the n-ary tree, and therefore has a time complexity of O(n).

1