# Maximum Depth of Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-depth-of-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/maximum-depth-of-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Infosys](https://scaleengineer.com/companies/infosys), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Spotify](https://scaleengineer.com/companies/spotify), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## 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 1:**

![](https://assets.glich.co/dsa/maximum-depth-of-binary-tree/image0.jpg) 

**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`

# Approaches
## Recursive Depth-First Search (DFS)
This is the most intuitive and common approach. It leverages the recursive nature of a tree. The maximum depth of a tree is defined as 1 (for the root) plus the maximum of the depths of its left and right subtrees.
**Time:** O(N) · **Space:** O(H)
**Pros:** The code is very concise, elegant, and easy to understand.; It directly models the recursive definition of a tree's depth.
**Cons:** For extremely deep trees, it might lead to a `StackOverflowError` due to deep recursion.; Can be less space-efficient than BFS for very skewed trees where the height approaches the number of nodes.
### Explanation
The algorithm works by defining a function that calculates the depth of a subtree rooted at a given node.
*   **Base Case:** If the current node is `null`, it represents an empty tree or the end of a path, which has a depth of 0.
*   **Recursive Step:** For a non-null node, we recursively call the function on its left and right children to find the depths of the left and right subtrees (`leftDepth` and `rightDepth`).
*   The depth of the tree rooted at the current node is then `1 + Math.max(leftDepth, rightDepth)`. The `+1` accounts for the current node itself.
The process starts by calling this function with the root of the entire tree.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
```
### Algorithm
*   If the `root` node is `null`, return 0.
*   Calculate the depth of the left subtree by making a recursive call: `leftDepth = maxDepth(root.left)`.
*   Calculate the depth of the right subtree by making a recursive call: `rightDepth = maxDepth(root.right)`.
*   Return `1 + max(leftDepth, rightDepth)`.

## Iterative Breadth-First Search (BFS)
This approach uses an iterative, level-by-level traversal (BFS) to find the depth. The maximum depth is simply the total number of levels traversed. This method avoids recursion and is often more robust against very deep trees.
**Time:** O(N) · **Space:** O(W)
**Pros:** Avoids recursion, thus preventing `StackOverflowError` on very deep trees.; Can be more space-efficient than DFS for tall and skinny trees (e.g., a linked list-like tree).
**Cons:** Generally requires more code than the recursive solution.; Can be less space-efficient than DFS for wide and shallow trees (e.g., a complete binary tree where the last level has ~N/2 nodes).
### Explanation
We use a queue to store nodes that need to be visited.
*   We start by adding the `root` to the queue. If the root is `null`, the depth is 0.
*   We then iterate level by level. A `depth` counter is incremented for each level.
*   In each iteration of the main loop, we process all nodes at the current level. We find the number of nodes at the current level (`levelSize = queue.size()`) before starting to process them.
*   We then dequeue `levelSize` nodes, and for each node, we enqueue its non-null children.
*   This process continues until the queue is empty, at which point the `depth` variable holds the maximum depth of the tree.
```java
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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 currentNode = queue.poll();
                
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
        }
        
        return depth;
    }
}
```
### Algorithm
*   Handle the edge case: if `root` is `null`, return 0.
*   Initialize a `Queue` and add the `root` to it.
*   Initialize a `depth` counter to 0.
*   Loop while the queue is not empty:
    *   Increment `depth`.
    *   Get the current level's size: `levelSize = queue.size()`.
    *   Loop `levelSize` times:
        *   Dequeue a node.
        *   Enqueue its non-null left and right children.
*   Return `depth`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int maxDepth ( TreeNode root ) { if ( root == null ) { return 0 ; } int l = maxDepth ( root . left ); int r = maxDepth ( root . right ); return 1 + Math . max ( l , r ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth =
  function (root) {
    if (!root) return 0;
    const l = maxDepth(root.left);
    const r = maxDepth(root.right);
    return 1 + Math.max(l, r);
  };

```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def maxDepth ( self , root : TreeNode ) -> int : if root is None : return 0 l , r = self . maxDepth ( root . left ), self . maxDepth ( root . right ) return 1 + max ( l , r )
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth ( TreeNode * root ) { if ( ! root ) return 0 ; int l = maxDepth ( root -> left ), r = maxDepth ( root -> right ); return 1 + max ( l , r ); } };
```