# 0104. Maximum Depth

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0104-maximum-depth-of-binary-tree)

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.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in the tree is in the range `[0, 104]`.
* `-100 <= Node.val <= 100`
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Extension question of **Level-order traversal**.
{% endhint %}

While traversing the tree in level order, we need to **record the current level (depth)**.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # (base case)
        if not root: return 0
        if not root.left and not root.right: return 1
    
        # ==================================================
        #  Binary Tree                       (Iterative)   =
        # ==================================================
        # time  : O(n)
        # space : O(n), O(log(n)) for average case

        maxDepth = 0
        stack = [root]
        
        while stack:
            # loop through stack for current length, pop the first node
            for i in range(len(stack)):
                node = stack.pop( 0 )
                
                if node.left: stack.append(node.left)
                if node.right: stack.append(node.right)
                    
            maxDepth += 1
            
        return maxDepth
        
        '''
        # ==================================================
        #  Binary Tree                       (Recursive)   =
        # ==================================================
        # time  : O(n)
        # space : O(n), O(log(n)) for average case
        
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
        '''
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n), O(log(n)) for average case
     */

    public int maxDepth(TreeNode root) {
        /* base case */
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        
        int maxDepth = 0;
        Queue<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        
        while(!stack.isEmpty()) {
            int size = stack.size();
            
            for(int i=0 ; i<size ; i++) {
                TreeNode node = stack.remove();
                
                if(node.left != null) stack.add(node.left);
                if(node.right != null) stack.add(node.right);
            }
            
            maxDepth++;
        }
        
        return maxDepth;
    }
}
```

{% endtab %}
{% endtabs %}