Problem

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).

Examples

Example 1

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png)

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

Example 2

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png)

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^4].
  • The depth of the n-ary tree is less than or equal to 1000.

Solution

Method 1 – Depth-First Search (DFS)

Intuition

The maximum depth of an N-ary tree is the longest path from the root to any leaf. We can recursively compute the depth for each child and take the maximum.

Approach

  1. If the root is null, return 0.
  2. For each child of the root, recursively compute its depth.
  3. The depth of the tree is 1 plus the maximum depth among all children.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

type Node struct {
    Val int
    Children []*Node
}
func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    ans := 0
    for _, c := range root.Children {
        d := maxDepth(c)
        if d > ans {
            ans = d
        }
    }
    return ans + 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int ans = 0;
        for (Node c : root.children) {
            ans = Math.max(ans, maxDepth(c));
        }
        return ans + 1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun maxDepth(root: Node?): Int {
        if (root == null) return 0
        var ans = 0
        for (c in root.children) {
            ans = maxOf(ans, maxDepth(c))
        }
        return ans + 1
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        ans = 0
        for c in root.children:
            ans = max(ans, self.maxDepth(c))
        return ans + 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<Node>>>) -> i32 {
        fn dfs(node: Option<Rc<RefCell<Node>>>) -> i32 {
            if let Some(n) = node {
                let n = n.borrow();
                let mut ans = 0;
                for c in &n.children {
                    ans = ans.max(dfs(c.clone()));
                }
                ans + 1
            } else {
                0
            }
        }
        dfs(root)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    maxDepth(root: Node | null): number {
        if (!root) return 0;
        let ans = 0;
        for (const c of root.children) {
            ans = Math.max(ans, this.maxDepth(c));
        }
        return ans + 1;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes, since each node is visited once.
  • 🧺 Space complexity: O(h), where h is the height of the tree, due to recursion stack.