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

Target Sum | Backtracking Problem

Introduction: In this tutorial we are going to solve a problem "Target Sum" which is from leetcode. and believe me it's really a good problem to understand Backtracking(Recursion). and if you try to understand the problem as well as code you will get a clear picture of Backtracking. Problem Statement: Link To Problem You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and - . For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Solution: As given in question, we have two operation + and -. so we will make recursive call for + and - . and if we have sum as target and we have reached upto the last ind...
Post a Comment
Read more

Group Anagrams solution with explanation:Leetcode solution

what is Anagrams? suppose we have two strings and the characters present in both of the strings are same. then both will be called anagram of each other. eg:" rat" and "art" both are anagram of each other. the characters present in both string are same. eg: "raat" and "art" these are not anagrams of each other. and the reason is that the frequency of "a" in "raat" is 2. while the frequency of "a" in "art" is 1. so these are not anagrams of each other. in short two strings will be anagram of each other if they have same characters and the count(frequency) of each and every character must be same in both strings. Solution: There are different ways to solve this question, so here we are going to use Hashmap to solve this question. cause whenever there is need to search we should go with the data structure which use balanced binary tress or hashing. and we know that Hashmap  uses balanced binary trees. so using...
Post a Comment
Read more