Maximum Depth of N-ary Tree
Easy · Trees · Tree · Depth-First Search · Breadth-First Search
Problem
Given the root of an n-ary tree (each node may have any number of children), return its maximum depth: the number of nodes on the longest path from the root down to the farthest leaf. An empty tree has depth 0.
Trees are written in level order: the root, then null, then the children of each node in turn, each group followed by null. For example [1,null,3,2,4,null,5,6] is a root 1 with children 3, 2 and 4, where 3 has children 5 and 6.
Examples
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
The path 1 -> 3 -> 7 -> 11 -> 14 has 5 nodes, the longest from the root to a leaf.
Input: root = [1,null,3,2,4,null,5,6] Output: 3
The path 1 -> 3 -> 5 has 3 nodes.
Input: root = [] Output: 0
An empty tree has depth 0.
Constraints
- The number of nodes is in the range [0, 10^4]
- 0 <= Node.val <= 10^4
- The depth of the tree is at most 1000
Approaches
- Baseline: walk every leaf up to the root — time O(n · h), space O(n)
Follow-up
The same level walk answers many "per level" questions: the width of the widest level, the sum of the deepest level, the values seen from one side. The longest path between any two nodes needs heights instead, combined at every node; both are use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
