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
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.
|
|
Dry Run
Code
|
|
Complexity
- Time Complexity: O(n) where n is number of nodes in tree
- Space Complexity: O(1)
Method 2 - Iterative Approach Using BFS
We can also use Binary Tree Traversal - Level Order OR BFS to find max depth as well.
|
|