Skip to main content

Validate Binary Search Tree | Leetcode(easy solution)

Introduction:
In this tutorial we will try to solve this question from leetcode. and this is also an important question for coding interview. so let's see this problem and try to solve it.

Problem Statement:

We have given a Binary Tree. and then we have to find out whether it is also Binary Search Tree or Not?
I hope you understand the difference between Binary Tree and Binary Search Tree.


Solution:
There are many ways to solve this problem, but we will see the most easy and efficient way.
So if you know about different kind of traversal(Inorder, Preorder and Postorder) of Binary Tree, then you can easily solve this problem.

To solve this problem, we will use Inorder traversal. In Inorder traversal we first traverse the left part then root and then right part of the tree.

Trick: Inorder traversal of Binary Search Tree will be in sorted order. it means, if we find the Inorder traversal of any Binary Search Tree, then it will be in sorted order.

so we will use this trick to solve this problem. first of all we will find the Inorder traversal of given Binary Tree and then check either it is in sorted order or not. if it is in sorted order then the given BT will be BST also, otherwise not.

Image:




Full Code:

  void inorder(TreeNode *root,vector<int>&v){
        if(root==NULL)
            return;
        inorder(root->left,v);
        v.push_back(root->val);
        inorder(root->right,v);
    }
    bool isValidBST(TreeNode* root) {
        if(root==NULL)
            return true;
  
        vector<int>v;
        inorder(root,v);
        if(v.size()==1){
            return true;
        }
        int flag=0;
     for(int i=0;i<v.size()-1;i++){
         if(v[i]>=v[i+1]){
             flag=1;
             break;
         }
     }
        if(flag==1){
            return false;
        }
        else{
            return true;
        }
    }

so basically what i am doing in my code is, i am traversing the given Binary Tree using Inorder traversal and then putting it into a vector. then checking that the vector is sorted or not using a for loop. if vector is sorted then i am returning True, otherwise return False.

if you have any query, comment it in comment section. i will try to solve your query.
best of luck.

Comments

Post a Comment

Popular posts from this blog

Disjiont Set Union-Find Data Structure | Code In C++

 Introduction:  In this tutorial we are going to write full program of disjoint set union find advance data structure in c++.  Problem Description: Disjoint Set Union (DSU) is an advance data structure, which basically uses in graph algorithms to find cycles. Codes:  Method1: Brute Force #include<bits/stdc++.h> using namespace std; int find(int f,vector<int>&dsuf){     if(dsuf[f]==-1)         return f;     return find(dsuf[f],dsuf); } void union_op(int from, int to, vector<int>& dsuf){     dsuf[from]=to; } bool isCycle(vector<pair<int,int> >&edge_list, vector<int>&dsuf){     for(int i=0;i<edge_list.size();i++){         int parent1=find(edge_list[i].first,dsuf);         int parent2=find(edge_list[i].second,dsuf);         if(parent1==pare...
Post a Comment
Read more

Linked List Data Structure | Add Two Number Explanation

Introduction: In this tutorial, we are going to solve a very famous problem on Linked List. It is also an important question for coding interview. so let's see the problem and understand it in detail. Problem Statement: There are two numbers and each digit of number is represented by a node of linked list.and we have to add these two numbers, which is given in the form of linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 eg: num1 = 2354;       num2 = 875; see the image below: Solution: Now let's solve it. In this problem there may be three possibilities. First: Number of Nodes in the first linked list is greater than second linked list. Second: Number of Nodes in first linked list is less than second list. Third: Number of Nodes in the both linked list is equal. Here number of nodes means number of digits in both number. Another thing we have to keep in mind is that if we add two digits then there may be possibility of gen...
Post a Comment
Read more

Integrating Frontend to Backend | MERN stack(100% working)

How to Integrate frontend to backend in MERN stack? For integrating the frontend to backend just do two things. Step1: Go and install cors on both side (front end as well as backend)              To install cors simply open the folder into terminal and type npm install cors--save. step 2: just go to your front end section(react app) open package.json file.                 and just add one line into package.json file.           "proxy":"http://localhost:4000" here i am using 4000, so what is 4000 ?. this is the port  on which our backend is listening. so it may be possible that u may have other port number on which your server is listening. so put yours port number on which your backend server is listening. and this proxy thing we have to add in frontend part not in backend part. Now it may be possible that you want to know ...
Post a Comment
Read more