problemeasyalgorithmsleetcode-559leetcode 559leetcode559

Maximum Depth of N-ary Tree

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

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


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

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

Example 2


![](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

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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)
    }
}
TypeScript
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.

Comments