Problem Statement:
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.
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
- The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100
Approach 1: (Top-Down)
- Start with the root node at depth
1. Traverse leftand right children, increasing depth at each level.- Keep track of the maximum depth encountered during traversal.
- Edge Case: If tree is empty (root is null),
return 0.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
1
/ \
2 3
\
4
Initialize:
maxDepth = 0
Call traversal(root, 1)
→ curr = 1, depth = 1
→ maxDepth = max(0, 1) = 1
→ curr.left = 2 → call traversal(2, 2)
→ curr = 2, depth = 2
→ maxDepth = max(1, 2) = 2
→ curr.left = null → no call
→ curr.right = 4 → call traversal(4, 3)
→ curr = 4, depth = 3
→ maxDepth = max(2, 3) = 3
→ curr.left = null → no call
→ curr.right = null → no call
→ Back to curr = 2 → done
→ Back to curr = 1
→ curr.right = 3 → call traversal(3, 2)
→ curr = 3, depth = 2
→ maxDepth = max(3, 2) = 3
→ curr.left = null → no call
→ curr.right = null → no call
→ Back to curr = 1 → done
Traversal complete.
Final maxDepth = 3
Output: Result: 3
var maxDepth = function(root) {
if(!root) return 0;
let maxDepth = 0;
let traversal = (curr, depth) => {
maxDepth = Math.max(maxDepth, depth);
curr.left && traversal(curr.left, depth + 1);
curr.right && traversal(curr.right, depth + 1);
}
traversal(root, 1);
return maxDepth;
};
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
return max(maxDepth(root.left), maxDepth(root.right)) + 1
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int maxDepth(TreeNode* root) {
if (!root) return 0;
return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int max(int a, int b) {
return a > b ? a : b;
}
int maxDepth(struct TreeNode* root) {
if (!root) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return max(left, right) + 1;
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int MaxDepth(TreeNode root) {
if (root == null) return 0;
return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
}
}
Approach 2: Bottom Up
- Base Case: If the node is null, return 0 — it means we've reached beyond a leaf node.
- Recursive Case:
- Recursively find the max depth of the
leftsubtree. - Recursively find the max depth of the
rightsubtree.
- Recursively find the max depth of the
Return 1 + the maximumof left and right subtree depths.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
1 / \ 2 3 \ 4 Recursive Calls: → maxDepth(1) → leftMax = maxDepth(2) → leftMax = maxDepth(null) = 0 → rightMax = maxDepth(4) → leftMax = maxDepth(null) = 0 → rightMax = maxDepth(null) = 0 → return 1 + max(0, 0) = 1 → return 1 + max(0, 1) = 2 → rightMax = maxDepth(3) → leftMax = maxDepth(null) = 0 → rightMax = maxDepth(null) = 0 → return 1 + max(0, 0) = 1 → return 1 + max(2, 1) = 3
Output: Result: 3
var maxDepth = function(root) {
if(!root) return 0;
let leftMax = maxDepth(root.left);
let rightMax = maxDepth(root.right);
return 1 + Math.max(leftMax, rightMax);
};
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
leftMax = maxDepth(root.left)
rightMax = maxDepth(root.right)
return 1 + max(leftMax, rightMax)
class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
return 1 + Math.max(leftMax, rightMax);
}
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
int maxDepth(TreeNode* root) {
if (!root) return 0;
int leftMax = maxDepth(root->left);
int rightMax = maxDepth(root->right);
return 1 + std::max(leftMax, rightMax);
}
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
int maxDepth(struct TreeNode* root) {
if (root == NULL) return 0;
int leftMax = maxDepth(root->left);
int rightMax = maxDepth(root->right);
return 1 + (leftMax > rightMax ? leftMax : rightMax);
}
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
public int MaxDepth(TreeNode root) {
if (root == null) return 0;
int leftMax = MaxDepth(root.left);
int rightMax = MaxDepth(root.right);
return 1 + Math.Max(leftMax, rightMax);
}
