Problem
Given a binary tree, find its maximum depth.
Definition
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.
The number of nodes along the longest path from the root node down to the farthest leaf node. Depth of root node is 0.
Examples
Example 1
graph TD; A(3):::blue --- B(9):::blue & C(20):::blue C --- D(15):::blue & E(7):::blue classDef blue fill:#0000FF,stroke:#000,stroke-width:1px,color:#fff;
|
|
Example 2
|
|
Example 2
|
|
|
|
Solution
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Method 1 - Recursive using Post order traversal
Intuition
This is same as the number of nodes in the longest path. We can see that longest path with just one node is 1 i.e. the node itself. So, height aka max depth aka longest path is one more than the max of left or right sub tree height.
|
|
Approach
We can implement this with a top-down recursive function.
- The base case for the recursion is a
null
node. If the node isnull
, it has no depth, so we return 0. - For any other node, we make two recursive calls: one to find the maximum depth of the left subtree, and another for the right subtree.
- We take the
max
of the two depths returned by the children’s subtrees and add 1 to it to account for the current node. - The final answer is the result of calling this function on the root of the tree.
Dry Run
Code
|
|
|
|
Complexity
- ⏰ Time Complexity:
O(n)
, wheren
is the number of nodes in the tree - 🧺 Space Complexity:
O(h)
, whereh
is the height of the tree (due to recursion stack; worst caseO(n)
for skewed tree)
Method 2 - Iterative DFS
Intuition
We can simulate the call-stack-based recursion of DFS with our own explicit stack. This avoids potential recursion depth limits and gives us direct control over the traversal. To find the maximum depth, we can’t just store the nodes; we must also store their depth relative to the root. This turns the traversal into a search for the node with the highest depth value.
Approach
- Create a stack to store pairs of
(node, depth)
. - Initialize the stack by pushing the
root
node with a starting depth of1
. - Initialize a variable
max_depth
to 0 to track the maximum depth found so far. - Loop as long as the stack is not empty:
a. Pop a
(node, depth)
pair from the stack. b. Updatemax_depth = max(max_depth, depth)
. c. If the node’s children are not null, push them onto the stack with an incremented depth (depth + 1
). To mimic a pre-order traversal, it’s conventional to push the right child first, then the left. - Return
max_depth
.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time Complexity:
O(n)
, wheren
is the number of nodes in the tree - 🧺 Space Complexity:
O(h)
, whereh
is the height of the tree (explicit stack; worst caseO(n)
for skewed tree)
Method 3 - Iterative Approach Using BFS
Intuition
We can also use Binary Tree Traversal - Level Order OR BFS to find max depth as well.
The maximum depth of a tree is simply the total number of levels it contains. A Breadth-First Search (BFS) is the perfect tool for this, as it naturally explores a tree one level at a time. By counting the number of levels we traverse, we can find the maximum depth.
Approach
- Create a queue and add the
root
node to it. - Initialize a
depth
counter to 0. - Loop as long as the queue is not empty. This outer loop represents traversing one level at a time.
a. Get the number of nodes on the current level (
level_size
). b. Create an inner loop that runslevel_size
times to ensure we only process nodes from the current level. c. In the inner loop, dequeue a node and enqueue its left and right children if they exist. d. After the inner loop finishes, we have completed a full level, so we increment thedepth
counter. - Once the queue is empty,
depth
will hold the total number of levels, which is the maximum depth.
Code
|
|
|
|
Complexity
- ⏰ Time Complexity:
O(n)
, wheren
is the number of nodes in the tree - 🧺 Space Complexity:
O(w)
, wherew
is the maximum width of the tree (worst caseO(n)
for a complete tree)