> For the complete documentation index, see [llms.txt](https://chunhthanhde.gitbook.io/leetcode-top-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-9-binary-tree-general/068-maximum-depth-of-binary-tree.md).

# 104. Maximum Depth of Binary Tree 🔗

**Difficulty**: `Easy` - **Tags**: `Binary Tree`, `DFS`, `BFS`

[LeetCode Problem Link](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

***

## 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**:

![](https://1796379692-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FXXeIX5WFjwBX14tD3BWy%2Fuploads%2Fgit-blob-2e654bc9176f09a0df9792fcfb91aa27b81aa8aa%2Ftmp-tree.jpg?alt=media)

**Input**:

```plaintext
root = [3,9,20,null,null,15,7]
```

**Output**:

```plaintext
3
```

***

🔹 **Example 2**:

**Input**:

```plaintext
root = [1,null,2]
```

**Output**:

```plaintext
2
```

***

## Constraints ⚙️

* The number of nodes in the tree is in the range `[0, 10⁴]`.
* `-100 <= Node.val <= 100`.

***

## Solution 💡

To determine the maximum depth of the binary tree, we can use two common approaches:

1. **Depth-First Search (DFS)**: Traverse the tree recursively and calculate the depth at each level.
2. **Breadth-First Search (BFS)**: Use a queue to traverse level by level, tracking the depth.

***

### Java Solution (Recursive DFS)

```java
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0; // Base case: An empty tree has a depth of 0
        }
        int leftDepth = maxDepth(root.left);  // Depth of left subtree
        int rightDepth = maxDepth(root.right); // Depth of right subtree
        return Math.max(leftDepth, rightDepth) + 1; // Add 1 for the root node
    }
}
```

***

### Java Solution (Iterative BFS)

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0; // Base case: An empty tree has a depth of 0
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size(); // Number of nodes at the current level
            for (int i = 0; i < size; i++) {
                TreeNode currentNode = queue.poll();
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            depth++; // Increment depth after processing one level
        }

        return depth;
    }
}
```

***

## Explanation of the Solution

1. **Recursive DFS**:
   * At each node, compute the depth of the left and right subtrees recursively.
   * The maximum depth at any node is `1 + max(leftDepth, rightDepth)`.
2. **Iterative BFS**:
   * Use a queue to traverse the tree level by level.
   * Each level's nodes are processed, and their children are added to the queue.
   * Increment the depth counter after processing each level.

***

## Time Complexity ⏳

* **DFS**: O(n), where `n` is the number of nodes in the tree.
* **BFS**: O(n), since each node is visited exactly once.

## Space Complexity 💾

* **DFS**: O(h), where `h` is the height of the tree (stack space for recursion).
* **BFS**: O(n), for the queue to store nodes at each level.

***

## Follow-up 🧐

* Compare the performance of recursive DFS versus iterative BFS for very large trees.
* Consider using a stack-based iterative DFS implementation for avoiding stack overflow in deep trees.

You can find the full solution: to-learn [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%209%20Binary%20Tree%20General/68%20Maximum%20Depth%20of%20Binary%20Tree/Solution.java), to coding interview [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%209%20Binary%20Tree%20General/68%20Maximum%20Depth%20of%20Binary%20Tree/Solution2.java).