559 Maximum Depth of N-ary Tree

1. Description

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. N-ary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.

 

constraints :

• The total number of nodes is in the range [0, \(10^{4}\)].
• The depth of the n-ary tree is less than or equal to 1000.

 

2. Algorithms

The N-ary tree have B-Tree form that elements in children node of current node are stored in list. To access all nodes in children, we need to access node by index.

 

For example, let's see when input root is [1, null, 3, 2, 4, null, 5, 6]. When we want to search node with 5, then our traversal will go as below :

root = root.children # [3, 2, 4]
root = root[0].children # [5, 6]
print(root[0].val) # 5

 

To find maximum depth of current node, we need to iterate through keys in current node.

 

1. Start
2. If root is None, return 0.
3. If the length of childnode is 0, return 1. (This because the total number of nodes start from 0.)
4. Return the max depth between all childnodes' depth adding 1 recursively.
5. End

 

3. Codes

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def maxDepth(self, root: 'Node') -> int: 
        if root is None : 
            return 0
        if len(root.children) == 0 : 
            return 1
        return 1 + max([self.maxDepth(child) for child in root.children])

4. Conclusion