0559. Maximum Depth

Easy | Tree + Level-order Traversal | 40 ms (93.70%), 16 MB (46.68%)

❓ Problem Statement

Source: LeetCode - Maximum Depth of N-ary Tree GitHub: Solution / Performance

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.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

✍🏻 Constraints & Example

Constraints:

• The total number of nodes is in the range [0, 104].

• The depth of the n-ary tree is less than or equal to 1000.

💡 Ideas

Extension question of Level-order traversal.

While traversing the tree in level order, we need to record the current level (depth).

🤖 Python3

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # (base case)
        if not root: return 0
        if not root.children: return 1
        
        # ==================================================
        #  N-ary Tree + Level Order Traversal              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        maxDepth = 0
        stack = [root]
        
        while stack:
            for i in range(len(stack)):
                node = stack.pop(0)
                
                for element in node.children:
                    stack.append(element)
            
            maxDepth += 1
            
        return maxDepth

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public int maxDepth(Node root) {
        /* base case */
        if(root == null) return 0;
        if(root.children == null) return 1;
        
        int maxDepth = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i=0 ; i<size ; i++) {
                Node node = queue.remove();
                
                if(node.children != null) {
                    for(Node element: node.children) queue.add(element);
                }
            }
            
            maxDepth++;
        }
        
        return maxDepth;
    }
}