> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/trees/binary]
> [project group:: neetcode 150]
> [difficulty:: easy]
> [status:: done]
> [link:: https://leetcode.com/problems/maximum-depth-of-binary-tree/]
> [up:: [[Leetcode MOC]]]
## 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:**
**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`
## Solution
### Mine
#### DFS
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
```
#### BFS
#### Iterative
### Neetcode
#### Iterative DFS
Use stack here, in the stack, a list or tuple of node, depth pairs
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
stack = [[root, 1]]
max_depth = 0
while stack:
node, depth = stack.pop()
if node:
max_depth = max(max_depth, depth)
stack.append([node.left, depth + 1])
stack.append([node.right, depth + 1])
return max_depth
```
#### DFS
O(n), worst case size O(n)
Base case: empty tree: 0
one you recurse back: 1 + max(L, R)
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
```
#### Iterative BFS
Not really any benefit, O(n) time and O(n) space
Basically counting the numbers we have
Uses queue/deque
Add first level to queue, get length, replace it with children, repeat
```python
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
level = 0
q = deque([root])
while q:
for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1
return level
```
## Things I Learned
## Scratchpad
This seems like a depth-first search problem.
Base case: No children, return counter(?)
Recursive case: current node has at least one child
What I'm not sure is how to preserve the depth counter
Or just try creating a stack