# 104. Maximum Depth of Binary Tree — LeetCode(Python)

I got you!

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

## 1. Recursive —

## Explanation —

We can easily solve this problem using bottom-up recursion.

If we know the height of the left and right subtrees, we can calculate the height of our current node by simply adding 1 to the greater height.

So, we recursively call the function on both left and right subtrees and return the updated answer.

## Time and Space Complexity —

Since we are visiting all nodes in the tree a constant number of times, we can say that our algorithm requires a linear amount of time to run.

Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.

Thus, if *n* is the number of nodes in the given binary tree,

Time Complexity: O(n)

Space Complexity: O(n)

## 2. Iterative —

## Explanation —

We can use a breadth-first search instead of a depth-first search to solve this problem iteratively.

We write a standard BFS traversal algorithm and keep storing the nodes in our tree level-wise in a *queue.*

Then, we keep *popping / enqueueing* from the ** queue** until a level is fully traversed and while doing so, we add nodes in the next level to our

*queue.*After every level traversed, we increment the value of *levels.*

Finally, we return *levels.*

## Time and Space Complexity —

Since we are visiting each node in the tree only a constant number of times, we can say that our algorithm requires linear amount of time to run.

Also, our queue will be storing a maximum of (n / 2) nodes when it reaches the final level. So, we assume the space complexity to be linear in the worst case.

Thus, if n is the number of nodes in the tree.

Time Complexity: O(n)

Space Complexity: O(n)