Course4all
Join us on telegram
Home/dsa/Trees/Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

Master this topic with zero to advance depth.

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

Easy

Examples

Input: root = [3,9,20,null,null,15,7]
Output: 3
Approach 1

Level I: Recursive DFS (Post-order)

Intuition

Max depth is 1+max⁡(depth of left child,depth of right child)1 + \max(\text{depth of left child}, \text{depth of right child}). This naturally fits recursion.

⏱ O(N)💾 O(H)

Detailed Dry Run

root(3) -> 1 + max(depth(9), depth(20)). depth(9)=1, depth(20)=2. Result = 3.

java
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}
Approach 2

Level II: Iterative BFS (Level Order)

Intuition

Traverse the tree level by level. Every completed level increases the depth.

Diagram

Level 1: [3] -> Depth 1 Level 2: [9, 20] -> Depth 2 Level 3: [15, 7] -> Depth 3
⏱ O(N)💾 O(W)

Detailed Dry Run

Queue: [3]. size=1. Pop 3, push 9,20. depth=1. Queue: [9,20]. size=2. Pop both, push 15,7. depth=2. Final depth=3.

java
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int depth = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            depth++;
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
        return depth;
    }
}
Approach 3

Level III: Iterative DFS (Stack)

Intuition

Manually manage a stack to mimic recursion. Store pairs of (node, depth) to keep track of max depth.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [(3,1)]. Pop (3,1), Max=1. Push (20,2), (9,2). Pop (9,2), Max=2. Pop (20,2), Push(7,3), (15,3). Pop (15,3), Max=3.

java
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 1));
        int maxDepth = 0;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> curr = stack.pop();
            TreeNode node = curr.getKey();
            int d = curr.getValue();
            maxDepth = Math.max(maxDepth, d);
            if (node.left != null) stack.push(new Pair<>(node.left, d + 1));
            if (node.right != null) stack.push(new Pair<>(node.right, d + 1));
        }
        return maxDepth;
    }
}
← Previous QuestionInvert Binary Tree
Next Question →Same Tree