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:
[0, 104].1000.Problem Overview: You receive the root of an N-ary tree where each node can have multiple children. The task is to compute the maximum depth of the tree, defined as the number of nodes along the longest path from the root node down to the farthest leaf node.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
The recursive DFS approach walks down each branch of the tree and tracks the deepest path encountered. Starting from the root, recursively compute the depth of every child node using a function call like depth(child). The depth of the current node equals 1 + max(child depths). If a node has no children, its depth is 1. This approach works naturally with trees because recursion mirrors the hierarchical structure. Time complexity is O(n) since each node is visited exactly once. Space complexity is O(h), where h is the height of the tree, due to the recursion stack. This method is the most concise and is commonly used when working with Tree recursion patterns.
Approach 2: Iterative Breadth-First Search (BFS) (Time: O(n), Space: O(w))
The BFS approach computes depth level by level using a queue. Start by pushing the root node into the queue. Each iteration processes all nodes at the current level, then pushes their children into the queue for the next level. After finishing one level, increment a depth counter. Once the queue becomes empty, the counter represents the maximum depth. This technique is a classic Breadth-First Search level-order traversal. Time complexity remains O(n) because every node enters and leaves the queue once. Space complexity is O(w), where w is the maximum number of nodes at any level (tree width). BFS is useful when you want explicit level tracking or when recursion depth might become large.
Both methods traverse the entire tree and produce the same result. DFS focuses on exploring deep paths first, while BFS expands outward level by level. These patterns appear frequently in Depth-First Search and tree traversal interview questions.
Recommended for interviews: Recursive DFS is usually the expected solution because it is short, intuitive, and directly expresses the definition of tree depth. BFS demonstrates strong understanding of level-order traversal and queue-based tree processing. Showing DFS first and mentioning BFS as an alternative signals solid tree traversal knowledge.
This approach leverages the recursive nature of trees to calculate the depth. For each node, if it has no children, it is a leaf and has depth 1. Otherwise, recursively calculate the depth of each child and take the maximum depth found among all children, adding 1 for the current node to account for the path to parent.
The function maxDepth is implemented recursively. We check if the root is None and return 0 which indicates an empty tree. If the node has no children, return 1, indicating it is a leaf. For a node with children, recursively calculate the max depth for each child and add 1 to the result to represent the current node.
The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited once. The space complexity is O(h) where h is the height of the tree, representing the function call stack during the recursion.
This approach utilizes BFS using a queue to iteratively compute tree depth. Nodes are enqueued level by level. At each level, we count its nodes, dequeuing them and enqueueing their children, indicating traversing to the next tree level. We increment a level counter as we progress deeper into the tree.
We use a deque to facilitate breadth-first traversal. In each loop iteration, we process all nodes at the current level and enqueue their children. Each iteration over the level represents moving a depth deeper, and we count these iterations to find the final maximum depth.
The time complexity is O(n) as we process each node once. The space complexity is O(n) for holding nodes of the widest level in the queue.
First, we check if root is null. If it is, we return 0. Otherwise, we initialize a variable mx to record the maximum depth of the child nodes, then traverse all the child nodes of root, recursively call the maxDepth function, and update the value of mx. Finally, we return mx + 1.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) Approach | The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited once. The space complexity is O(h) where h is the height of the tree, representing the function call stack during the recursion. |
| Iterative Breadth-First Search (BFS) Approach | The time complexity is O(n) as we process each node once. The space complexity is O(n) for holding nodes of the widest level in the queue. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Preferred for interviews and typical tree recursion problems |
| Iterative Breadth-First Search (BFS) | O(n) | O(w) | Useful when processing trees level-by-level or avoiding deep recursion |
Breadth First Search & Depth First Search | Maximum Depth of N-ary Tree | LeetCode 559. • Nick White • 27,711 views views
Watch 9 more video solutions →Practice Maximum Depth of N-ary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor