Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 3
Example 2:
Input: root = [1,null,2] Output: 2
Constraints:
[0, 104].-100 <= Node.val <= 100The goal of #104 Maximum Depth of Binary Tree is to determine the number of levels in a binary tree from the root node to the deepest leaf. A common way to approach this problem is by exploring the tree structure and keeping track of the longest path.
One effective strategy uses Depth-First Search (DFS). Starting from the root, recursively explore the left and right subtrees. At each node, compute the depth of both children and return 1 + max(leftDepth, rightDepth). This approach naturally fits the recursive nature of trees and is often the most intuitive solution in interviews.
Another option is Breadth-First Search (BFS) using a queue. Process the tree level by level, increasing a counter after finishing each level. When the queue becomes empty, the counter represents the tree’s maximum depth.
Both methods visit every node once, making them efficient solutions. The choice typically depends on whether you prefer recursive traversal (DFS) or iterative level-order traversal (BFS).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (Recursive) | O(n) | O(h) |
| Breadth-First Search (Level Order) | O(n) | O(n) |
NeetCode
This approach involves using a recursive function that traverses the tree in a depth-first manner. For each node, calculate the maximum depth of its left and right subtrees, and add 1 for the current node itself. The function returns the maximum of these two values. This provides an elegant and intuitive solution, leveraging the inherent recursive structure of trees.
Time Complexity: O(n) where n is the number of nodes, as each node is visited once.
Space Complexity: O(h) where h is the height of the tree, due to the stack space in recursion.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left
In JavaScript, similar strategies apply, using recursive function calls to determine the maximum depth by comparing subtree depths. If the node is null, return 0.
This approach involves using a queue to perform a Breadth-First Search (BFS) on the tree. By iterating level by level, we increment the depth counter with each level traversed completely.
Time Complexity: O(n) due to each node being visited once.
Space Complexity: O(n) where n is the maximum number of nodes at any level.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, the problem can also be solved using Breadth-First Search (BFS). By traversing the tree level by level with a queue and counting the number of levels processed, you can determine the maximum depth of the tree.
Yes, this is a common interview question at companies like Google, Amazon, and Meta. It tests fundamental understanding of tree traversal techniques such as DFS and BFS and is often used as a warm-up tree problem.
Binary trees themselves are the core data structure in this problem. DFS solutions rely on recursion or a stack, while BFS solutions use a queue to process nodes level by level.
The optimal approach typically uses Depth-First Search (DFS) with recursion. By recursively computing the depth of the left and right subtrees and returning 1 plus the maximum of the two, you can determine the tree's maximum depth efficiently. This approach visits each node once, resulting in O(n) time complexity.
JavaScript implements Array-based queue-like structures for breadth-first traversal. The process entails checking node existence, pushing children into arrays, and incrementing depth post-level due completion.