DAY 56 - Binary Tree Questions(I)
Tags: leetcode, tutorial, algorithms, cpp
Published: 2023-07-29 18:38:41

Welcome to DAY 56. Today we will diverge once again into the Data Structure Trees and look at some more traversals. I suggest reading the previous [article](https://dev.to/pahujanayan/day-54-traversals-in-a-binary-tree-2oea) on Trees before reading this.

---

## Questions:

### [Maximum Depth of Binary Tree:](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/)

_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:_**


![Tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/337keavq5qxfs01d9f0s.png)

> - **Input:** root = [3,9,20,null,null,15,7]
> - **Output:** 3


---

### Algorithm and Code:
- So the question is basically asking us to find the height of binary tree.
- What's the height of a binary tree? It is the maximum level you can go to in the furthest leaf node.
- In our example we see 15 and 7 are the farthest from the root node.
- They are both at a height of 3.
- So We look at this in a recursive way, We don't need to find out the totalHeight. We can just find the max height bw Left and Right subtree and we can add 1 to that as the final node is root node.
- If you imagine this we can apply similar logic to left subtree's left subtree and so on and similarly for right subtree.
- Hence by using this logic we can find out max depth using this recursive approach.



```
int maxDepth(TreeNode* root) {
        if(root == NULL)
        {
            return 0;
        }
        int lh = maxDepth(root->left);
        int rh = maxDepth(root->right);
        return 1 + max(lh,rh);
 }
```


---

## Question: [Balanced Binary Tree](https://leetcode.com/problems/balanced-binary-tree/)

_Given a binary tree, determine if it is `height-balanced`_

`A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.`

---

**_Example 1:_**


![Tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g6mxki2ieiphms6tp4ue.png)



> - Input: root = [3,9,20,null,null,15,7]
> - Output: true

---

### Naïve Approach:
- We can either checkout the height at every node of the tree.
- If we find the absolute difference to be greater than 1 we return false.
- We use the code above to find the height of the subtrees and then We recursively check to find if each node is balanced.
- This is a good approach but we are taking a Time Complexity of O(n^2) to find our result as we are finding height in o(N) time for every node and traversing every node also takes O(N) time.
- This approach is not time efficient. 

---


### Code:

```
int maxDepth(TreeNode* root) {
        if(root == NULL)
        {
            return 0;
        }
        int lh = maxDepth(root->left);
        int rh = maxDepth(root->right);
        return 1 + max(lh,rh);
}
    bool isBalanced(TreeNode* root) {
        // base case
        if(root  == NULL)
        {
            return true;
        }

        bool lb = isBalanced(root->left);
        bool rb = isBalanced(root->right);
        bool diff = abs(maxDepth(root->left) - maxDepth(root->right)) <= 1;

        if(lb && rb && diff)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
```

---

**_Complexity Analysis:_**
**Time:** O(N^2)
**Space:** O(1)

---

### Better Approach:
- Instead of returning a height from our getHeight function or maxDepth function.
- How about we instead only get height if they are balanced.
- In the maxDepth function we are traversing the whole array anyway using the same logic.
- When we are finding the heights of left and right subtree of the node, why not instead of continuing we simply keep returning -1 which indicates it's not balanced.
- It removes the redundancy and also helps us out by optimizing the time.

### Code:

```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
        {
            return 0;
        }
        int lh = maxDepth(root->left);
        if(lh == -1) return -1;
        int rh = maxDepth(root->right);
        if(rh == -1) return -1;
        if(abs(rh - lh) > 1) return -1;
        return 1 + max(lh,rh);
}
    bool isBalanced(TreeNode* root) {
        return maxDepth(root) != -1;
    }
};
```

---

**_Complexity Analysis:_**
**Time:** O(N)
**Space:** O(1)