Day 5 (30 Days of Code)

4 July 2023

Today I only did Leetcode and somehow out of five questions, four were from binary trees so it was a good revision for me.

What did I learn?

There is nothing in particular that I learned today. However, I solved 5 questions in Leetcode in a day which is my highest until now.

1. Sqrt(x)

My approach:

I was able to identify the pattern so I was able to do the question in O(N) time complexity. However, when I looked at the solution there exists a solution at O(logn) time which can be achieved through binary search.

My Solution:

• Linear Complexity :

class Solution {
public:
    int mySqrt(int x) {

        if(x<2){
            return x;
        }

        int i = 1;

        while(i<=x){
            if(x/(i*i)==1 && x%(i*i) <= 2*i ){  // this line is where I used the pattern I indentified
                return i;
            }
            else if(x/(i*i)==0){
                return i-1;
            }
            else{
                i++;
            }
        }
        return i;
    }
};

• Optimized solution (logn):

    class Solution {
    public:
        int mySqrt(int x) {
  
            if(x==0){
                return 0;
            }
            int first = 1;
            int last = x;
            while(first<=last){
                int mid = first+ (last-first)/2;
                if(mid>x/mid){
                    last = mid-1;
                }
                else if(mid<x/mid){
                    first = mid+1;
                }else{
                    return mid;
                }
            }
            return last;
        }
    };
  

1. Same Tree

My approach:

For this, I used the simple recursion technique which I think is the best way to solve this question.

My solution:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL && q==NULL){
            return true;
        }
        if(p==NULL || q==NULL){
            return false;
        }

        if(p->val != q->val){
            return false;
        }

        bool ans1 = isSameTree(p->left,q->left);
        bool ans2 = isSameTree(p->right, q->right);

        if(ans1==false || ans2==false){
            return false;
        }
        else{
            return true;
        }
    }
};

1. Symmetric Tree

My approach:

Just like before I again used recursion but this time it was a little different than the way we use normally it. This question is somewhat similar to finding out if the two subtrees are mirror images of each other.

My solution:

class Solution {
public:

    bool helper(TreeNode* tree1, TreeNode* tree2){
        if(tree1==NULL && tree2==NULL){
            return true;
        }
        if(tree1==NULL || tree2==NULL){
            return false;
        }

        if(tree1->val!=tree2->val){
            return false;
        }

        bool ans1 = helper(tree1->left,tree2->right);
        bool ans2 = helper(tree1->right,tree2->left);

        if(ans1==false || ans2==false){
            return false;
        }
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL ){
            return true;
        }

        bool output = helper(root->left, root->right);
        return output;
    }
};

1. Maximum Depth of Binary Tree

My approach:

This question is pretty much similar to finding the height of a binary tree so it was easy to solve.

My solution:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL){
            return 0;
        }

        if(root->left==NULL && root->right==NULL){
            return 1;
        }

        int leftSide = maxDepth(root->left);
        int rightSide = maxDepth(root->right);

        return max(leftSide,rightSide)+1;
    }
};

1. Balanced Binary Tree

My approach:

In the beginning, I was making a logical mistake which was due to have only half knowledge about the balanced binary tree once I understood the real definition of the balanced binary tree I was able to do the rest.

My solution:

class Solution {
public:
    int height(TreeNode* rootSide){
        if(rootSide==NULL){
            return 0;
        }

        int ans1 = height(rootSide->left);
        int ans2 = height(rootSide->right);

        return 1+max(ans1,ans2);
    }
    bool isBalanced(TreeNode* root) {

        if(root==NULL){
            return true;
        }

        bool ans1 = isBalanced(root->left);
        bool ans2 = isBalanced(root->right);

        int leftSideHeight = height(root->left);
        int rightSideHeight = height(root->right);

        if((max(leftSideHeight,rightSideHeight)-min(leftSideHeight,rightSideHeight))>1){
            return false;
        }

        return ans1 && ans2;
    }
};

My first React app is now Live:

https://nirbhayimdb.netlify.app/