104. Maximum Depth of Binary Tree #
Problem #
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 #
Example 1: #
(3)
/ \
(9) (20)
/ \
(15) (7)
Input: root = [3,9,20,null,null,15,7]
Output: 3
Constraints #
- The number of nodes in the tree is in the range [0, 104].
- \( -100 <= Node.val <= 100 \)
Follow up #
Approach and Intuition #
1. Recursive traversal #
private int maxDepth_Recursive(TreeNode root){
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) +1;
}
Time Complexity:
\( O(n) \)
Space Complexity:
\( O(n) \)
2. Iterative BFS #
We can use BFS to get the highest level(deepest node). Implement BFS, return the size of the List of level nodes.
Check this question for more into on 102. Binary Tree Level Order Traversal
private int maxDepth_Iterative_BFS(TreeNode root){
List<List<Integer>> resultList = new ArrayList<>();
if(root == null) return 0;
TreeNode curr = root;
Queue<TreeNode> q = new LinkedList<>();
q.offer(curr);
while(!q.isEmpty()){
int qSize = q.size();
List<Integer> subList = new ArrayList<>();
for(int i=0; i< qSize; i++){
curr = q.poll();
subList.add(curr.val);
if(curr.left != null){
q.offer(curr.left);
}
if(curr.right != null){
q.offer(curr.right);
}
}
//add to main list
resultList.add(subList);
}
return resultList.size();
}
Time Complexity:
\( O(n) \)
Space Complexity:
\( O(n) \)
3. Iterative traversal using height variable #
private int maxDepth_usingHeightVariable(TreeNode root){
if(root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int maxDepth = 0;
while(!q.isEmpty()){
maxDepth++;
int i = q.size();
while(i-- > 0){
TreeNode curr = q.poll();
if(curr.left != null){
q.offer(curr.left);
}
if(curr.right != null){
q.offer(curr.right);
}
}
}
return maxDepth;
}
Time Complexity:
\( O(n) \)
Space Complexity:
\( O(n) \)
Related problems #
- 102. Binary Tree Level Order Traversal
- 987. Vertical Order Traversal of a Binary Tree
- 199. Binary Tree Right Side View
- 107. Binary Tree Level Order Traversal II
- 94. Binary Tree Inorder Traversal