DAY 56 - Binary Tree Questions(I)

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 on Trees before reading this.

Questions:

Maximum Depth of Binary Tree:

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

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

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:

• 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)