Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

**Example: **Given a binary tree

3 -------------- Depth : 1/\56 ----------- Depth : 2/ \ 2 7 -------- Depth : 3Depth = 3

First of all, here is the definition of the `TreeNode`

which we would use.

```
/* Definition for a binary tree node. */
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
```

By definition, the maximum depth of a binary tree is the maximum number of steps to reach a leaf node from the root node.

**Recursive Solution**

```
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int left_height = maxDepth(root.left);
int right_height = maxDepth(root.right);
return Math.max(left_height, right_height) + 1;
}
}
}
```

**Time Complexity:**We visit each node exactly once, thus the time complexity is`O(N)`

, where`N`

is the number of nodes.**Space Complexity:**In the worst case, the tree is completely unbalanced,*e.g.*each node has only left child node, the recursion call would occur`N`

times (the height of the tree), therefore the storage to keep the call stack would be`O(N)`

. But in the best case (the tree is completely balanced), the height of the tree would be`log(N)`

. Therefore, the space complexity, in this case, would be`O(log(N))`

.

**Iterative Solution**

We could also convert the above recursion into an iteration, with the help of the *Queue *data structure. The idea is to keep the next nodes to visit in a Queue. And calculate the height of the tree by another Queue.

```
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> depths = new LinkedList<>();
queue.offer(root);
depths.offer(1);
int depth = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int curDepth = depths.poll();
depth = Math.max(curDepth, depth);
if (node.left != null) {
queue.offer(node.left);
depths.offer(curDepth + 1);
}
if (node.right != null) {
queue.offer(node.right);
depths.offer(curDepth + 1);
}
}
return depth;
}
}
```

**Time Complexity:**`O(N)`

.**Space Complexity:**In the worst case, the tree is completely unbalanced,*e.g.*each node has an only left child node, the recursion call would occur`N`

times (the height of the tree), therefore the storage to keep the call stack would be`O(N)`

. But in the average case (the tree is balanced), the height of the tree would be`log(N)`

. Therefore, the space complexity, in this case, would be`O(log(N))`

.

Categories: Binary Tree