Algorithm-Day38-Maximum-Depth-of-Binary-Tree-lc-104

Posted on In , Views:

🧩 Problem Description

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

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

💡 Approach 1: Recursive DFS

We can recursively compute the depth of left and right subtrees, then take the maximum of the two.

🔢 Java Code (Recursive DFS)

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

💡 Approach 2: Iterative BFS (Level Order)

We can use a queue to perform level-order traversal and count how many levels exist.

🔢 Java Code (BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            depth++;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — visit every node once
  • Space Complexity:
    • Recursive: O(h) call stack
    • BFS: O(w) for the queue (w = max width of the tree)

✍️ Summary

  • Depth-first (recursive) is elegant and concise
  • Level-order (BFS) gives more control (e.g., per-level info)
  • Know both for interviews and practical use

Tree depth is foundational — used in balancing, recursion limits, and more.