Maximum Depth of N-ary Tree

EASY

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.

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

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 5

Constraints:

The total number of nodes is in the range [0, 10⁴].
The depth of the n-ary tree is less than or equal to 1000.

Approaches

Checkout 2 different approaches to solve Maximum Depth of N-ary Tree. Click on different approaches to view the approach and algorithm in detail.

Iterative Breadth-First Search (BFS)

This approach finds the maximum depth by traversing the tree level by level. It uses a queue to manage the nodes at each level and counts the number of levels traversed, which corresponds to the depth of the tree.

Algorithm

If the root is null, return 0.
Initialize a Queue and add the root node.
Initialize depth to 0.
While the queue is not empty:
- Get the number of nodes at the current level, levelSize.
- Increment depth.
- Loop levelSize times:
  - Dequeue a node.
  - Enqueue all of its children.
Return depth.

The algorithm works by performing a level-order traversal.

We start with a queue containing just the root node and initialize the depth to 0.
We then enter a loop that continues as long as there are nodes to process in the queue.
In each iteration of the loop, we process one full level of the tree. We first record the number of nodes currently in the queue (levelSize). These are all the nodes at the current depth.
We increment our depth counter because we are moving one level deeper.
We then dequeue levelSize nodes, and for each node, we enqueue all of its children. This prepares the queue with all nodes for the next level.
Once the queue is empty, it means we have visited all nodes, and the depth counter holds the maximum depth of the tree.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        
        int depth = 0;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            depth++;
            for (int i = 0; i < levelSize; i++) {
                Node currentNode = queue.poll();
                if (currentNode.children != null) {
                    for (Node child : currentNode.children) {
                        queue.offer(child);
                    }
                }
            }
        }
        
        return depth;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the total number of nodes. Each node is enqueued and dequeued exactly once.Space Complexity: O(W), where W is the maximum width of the tree. The space is used by the queue, which holds at most all nodes at the widest level. In the worst case (a complete, wide tree), the width W can be close to N.

Pros and Cons

Pros:

Avoids recursion, preventing potential StackOverflowError for extremely deep trees.
Can be more space-efficient than DFS for very deep and narrow trees.

Cons:

Can be less space-efficient than DFS for wide and shallow trees. For the given constraints, its worst-case space complexity (O(N)) is higher than DFS's (O(H)).
The implementation is slightly more verbose than the recursive solution.

Code Solutions

Checking out 3 solutions in different languages for Maximum Depth of N-ary Tree. Click on different languages to view the code.

/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public int maxDepth ( Node root ) { if ( root == null ) { return 0 ; } int ans = 1 ; for ( Node child : root . children ) { ans = Math . max ( ans , 1 + maxDepth ( child )); } return ans ; } }

Video Solution

Watch the video walkthrough for Maximum Depth of N-ary Tree

Algorithms:

Depth-First SearchBreadth-First Search

Data Structures:

Tree

Companies:

Datadog |