## Find The Height Of a Binary Tree

**Difficulty: **Easy

**Asked in: **Amazon, Goldman Sachs

#### Understanding The Problem

**Problem Description**

Given a binary tree, write a program to find the **maximum depth **of the binary tree.

**Problem Note**

- The
**maximum depth**is the number of nodes along the longest path from the root node to the leaf node. - A leaf is a node with no child nodes.

**Example**

```
Input: Given binary tree,
[5, 3, 6, 2, 4, -1, -1, 1, -1, -1, -1, -1, -1]
5
/ \
3 6
/ \
2 4
/
1
Output: return its depth = 4
```

#### Solutions

The height of a binary tree is the maximum distance from the root node to the leaf node. We can find the height of the binary tree in two ways.

**Recursive Solution**: In a recursive function, for each child of the root node, we can increment height by one and recursively find the height of the child tree.**Iterative Solution**: We can do a level order traversal and for each new level, we can increment the height by one.

The node structure passed to the function is:

```
struct TreeNode{
int val
TreeNode left
TreeNode right
}
```

You can try practising this problem here.

#### 1. Recursive Solution

To solve a tree's problems, recursive solutions are very intuitive. Like in this case, a very intuitive approach is to find the maximum of height from the left subtree and the right subtree of the root node and return the maximum height + 1.

In other words, We can define a subproblem as, If the root node has left child or right child then find the maximum height of the trees whose root is the left child and the right child. Add 1 to the maximum height of the children tree**(Why?).**

**Solution Steps**

- Check if the root is NULL then return 0
- Return the maximum(left subtree of root, right subtree of root) + 1

**Pseudo Code**

```
int maxDepth(TreeNode root) {
if(root){
height = max(maxDepth(root.left), maxDepth(root.right))
return height + 1
}
return 0
}
```

**Complexity Analysis**

Time Complexity: O(n)

Space Complexity: O(n)

**Critical Ideas To Think**

- Why did we add 1 with the height in pseudocode?
**Answer**: The root node itself contributes to the path of maximum height from root to leaf node. - Why space complexity is O(n)?
**Answer**: The tree can be skew, in such cases the recursion stack uses the space. - What is the base case for the recursion?
**Answer:**If the root is NULL then we return 0.**(Why?)**

#### 2. Iterative Solution

One can think of an iterative solution if you consider solving this problem using BFS traversal or Level Order Traversal. For each new level encountered while traversing from the root node, we can increment the height of the tree by one.

How can we implement level order traversal to find height?

We will take a Queue and add root to it. And we can initialize a variable `height`

to maintain the maximum height of the tree.

Now, we will dequeue all the nodes of the Queue from the front and will enqueue the left and right child of the dequeued nodes in the rear which represent the next level of the tree. For each such cycle, we can increment the height by one. We will continue doing this until no nodes left in the Queue.

**Solutions Steps**

- Create a Queue and push the root node in it
- Dequeue all the nodes of Queue and enqueue all the children of the dequeued nodes —

- For each such step, increment the height by 1

3. Repeat step 2 until the Queue becomes empty.

**Pseudo Code**

```
int maxDepth(TreeNode *root) {
// Base Case
if (root is NULL)
return 0
// Create an empty queue for level order tarversal
Queue q
q.push(root)
int height = 0
while (true) {
int currLevelNodes = q.size()
if (currLevelNodes == 0)
return height
height = height + 1
while (currLevelNodes > 0)
{
TreeNode node = q.front()
q.pop()
if (node.left is not NULL)
q.push(node.left)
if (node.right is not NULL)
q.push(node.right)
currLevelNodes = currLevelNodes - 1
}
}
}
```

**Complexity Analysis**

Time Complexity: O(n)

Space Complexity: O(n)

**Critical Ideas To Think**

- Why did we return the
`height`

only when`currLevelNode`

is 0? - Why did we pop all the nodes inside the Queue? How did that help us to filter the nodes of the current level and the next level of the tree?

#### Comparison of Different Solutions

#### Suggested Problems To Solve

- Find the average of levels of binary tree
- Postorder traversal of binary tree
- Level order traversal of Binary tree
- Iterative preorder traversal of Binary tree
- Find the nth node in the inorder traversal of binary tree

*Please comment down below if you have a better insight in the above approach.*

**Happy Coding, Enjoy Algorithms!**