• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Check Binary Tree is Binary Search Tree or not

July 29, 2014 by Dhaval Dave

To search Binary Search Tree
First lets understand characteristics of BST
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
• Each node (item in the tree) has a distinct key.
First Logic Comes in mind isMethod 1) For each node, check if left node of it is smaller than the node and right node of it is greater than the node.
But is wrong.
Take below Example which satisfies condition. but not a BST.

           [3]
          /   \
       [2]     [5]
      /   \    /  \
    [1]  [4] [0]  [8]

Method 2) Simply Print In Order Traversal of Tree and check all are in ascending order or not.
To optimize Storing of inorder traversal , we can check in place.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}
int isBST(struct node* root)
{
    static struct node *prev = NULL;
    if (root){
        if (!isBST(root->left))
          return 0;
        if (prev != NULL && root->data <= prev->data)
          return 0;
        prev = root;
        //To keep track of previous node Mark that its STATIC
        return isBST(root->right);
    }
    return 1;
}

int main(void) {
  //BST
  struct node *root = newNode(4);
  root->left        = newNode(2);
  root->right       = newNode(5);
  root->left->left  = newNode(1);
  root->left->right = newNode(3); 
  //Not A BST
  /*struct node *root = newNode(3);
  root->left        = newNode(2);
  root->right       = newNode(6);
  root->left->left  = newNode(1);
  root->left->right = newNode(5);
  */
  if(isBST(root))
    printf("Is BST");
  else
    printf("Not a BST");
  return 0;
}

Visit Full Working Code of Mehtod 2 at : http://ideone.com/e.js/3h1Q25

Now We can think like, If we have order and all nodes in increasing order then we can say its BST, We can think of an approch in which we pass min and max value so far in recursion.
and We can decide weather it is BST or not.

Algorithm would be similar to this

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, min_so_far, max_so_far)); 
} 

int isBSTUtil(struct node* node, int min_so_far, int max_so_far) 
/* Returns true if the given tree is a BST and its values are >= max_so_far and <= max_so_far. */

Code for above algorithm is

int isBST(struct node* node) 
{ 
  return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 
 
int isBSTUtil(struct node* node, int min, int max) 
{ 
  if (node==NULL) 
     return 1;
       
  if (node->data < min || node->data > max) 
     return 0; 
 
  return
    isBSTUtil(node->left, min, node->data-1) && isBSTUtil(node->right, node->data+1, max);  
}
As inOrder traversal of BST is in sorted order like 1,2,3,4,5.
I can think of approach in which I can keep just One variable Prev and find weather all nodes are larger than previous one or not.
If this condition fails, Its not BST, example : 1,3,2,4,5,6
initially when node’s data is 1, prev is Int_min, so condition satisfies
When node’s data is 3, prev is 1, so condition satisfies.
When node’s data is 2, prev is 2, so its not satisfying
See Code for above Logic

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
 
  return(node);
}
int isBST(struct node* root,int prev)
{
  if (!root) return 1;
  
  if (isBST(root->left, prev)) {
  	
    if (root->data > prev) {
      prev = root->data;
      return isBST(root->right, prev);
    } 
    else return 0;
  }
  else return 0;
}

int main(void) {
  //BST
  struct node *root = newNode(4);
  root->left        = newNode(2);
  root->right       = newNode(5);
  root->left->left  = newNode(1);
  root->left->right = newNode(3); 
  //Not A BST
  /*struct node *root = newNode(3);
  root->left        = newNode(2);
  root->right       = newNode(6);
  root->left->left  = newNode(1);
  root->left->right = newNode(5);
  */
  if(isBST(root,INT_MIN))
    printf("Is BST");
  else
    printf("Not a BST");
  return 0;
}
See working code at : http://ideone.com/e.js/HDWFLL

 

 

Similar Articles

Filed Under: Interview Questions, problem Tagged With: Binary Search Tree, Binary Tree, BST, tree

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

flattens 2 D linked list to a single sorted link list

simple sql injection

Common Ancestor in a Binary Tree or Binary Search Tree

Generic Object Oriented Stack with Template

Maximum size of square sub matrix with all 1’s in a binary matrix

Adobe Interview Questions 8 month Exp

Best Java Book | Top Java Programming Book for Beginners

Memory Efficient LinkedList

25 horses 5 tracks Find 3 fastest puzzle

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

C Program for TAIL command of UNIX

Linked List V/S Binary Search Tree

Get K Max and Delete K Max in stream of incoming integers

Printing each word reverse in string

VMWare SDEII Interview

BlueStone E-commerce Interview Experience

Print Power Set of a Set

Sort an array according to the order defined by another array

Find the smallest window in a string containing all characters of another string

Python String and numbers

FizzBuzz Solution C C++

Stock Buy Sell to Maximize Profit

Check if an array has duplicate numbers in O(n) time and O(1) space

Level order traversal in Spiral form

Templates in C++

Get Minimum element in O(1) from input numbers or Stack

HackeEarth Flipkart’s Drone

Find Percentage of Words matching in Two Strings

Reliance Jio Software Developer Interview Experience

Copyright © 2025 · Genesis Framework · WordPress · Log in