# Maximum Depth of Binary Tree

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
/  \
5    6 ----------- Depth : 2
/  \
2    7 -------- Depth : 3

Depth = 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.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