## Approach #1 DFS by Recursion [Accpeted]

**Intuition**

- We have to keep go further until we reach the leaves.
- We need 2 recursive calls for right subtree and left subtree.
- We use
`return`

value as depth- So each time we go deeper, we
`add 1`

to return value - When we reach the None-node,
`return 0`

(base case for recursion)

- So each time we go deeper, we
- different subtree may has different depth, and we use
`max`

to find longest depth

**Algorithm**

- check whether the current node is None
- make recursive calls and find
`max`

- add 1 to
`depth`

**Python**

```
def dfs(root):
if root is None:
return 0
go_left = dfs(root.left)
go_right = dfs(root.right)
return max(go_left, go_right) + 1
```

```
def dfs_concise(root):
return max(dfs_concise(root.left), dfs_concise(root.right)) + 1 if root is not None else 0
```

**Complexity Analysis**

- Time complexity : $$O(n)$$.

DFS will reach every node in tree, so it depends on the number of nodes in tree.

- Space complexity : $$O(1)$$.

We only need constant memory space for value which is returned by recursive calls.

## Approach #2 BFS by Queue [Accepted]

**Intuition**

- We want traverse this tree level by level, so we can add 1 to
`depth`

between levels. - We scan nodes in same level, if they have non-None subnode, we put them into
`queue`

. - Note that we have to remember how many nodes in this level so that we can aovid to get the node from the next level.

#### note: it is more likely to be level order traversal

**Algorithm**

- handle root and initialize queue
- if queue is not empty, we keep looping it
- we have to remember how many nodes in current level
- we pick first node in queue to check whether its subnode needs to be put in queue
- after scaning all nodes in the same level, we can add 1 to
`depth`

- we can proceed to next level if there is node in queue

**Python**

```
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
queue = [] # simulate list as queue
queue.append(root)
depth = 0 # root itself
while queue:
node_number_in_level = len(queue)
for _ in range(node_number_in_level):
front = queue.pop(0) # index 0 to pop first element
if front.left is not None:
queue.append(front.left)
if front.right is not None:
queue.append(front.right)
depth += 1 # we ran through this level
return depth
```

**Complexity Analysis**

- Time complexity : $$O(n)$$

`append()`

,`len()`

,`pop()`

: are all $O(1)$.

BFS will walk through all element in array once, although there is `for`

looop inside.

- Space complexity : $$O(n)$$

We need memory space for queue, which depends on the number of nodes in tree.