Home Data Structures Check if a Binary Tree is a Binary Search Tree

Check if a Binary Tree is a Binary Search Tree

Given a Binary Tree, we have to validate whether it is a valid Binary Search Tree(BST) or not. Print true, if given Binary Tree is a valid BST else print false.

Let’s understand this problem better with an example

          15
        /    \
      8       25
    /  \     /  \
   4   12   20   30

It's is valid Binary Serach Tree

         15
       /    \
     8       25
   /  \     /  \
  4   19   20   30

It's not a valid BST, becacuse node 19 is
voilating the property of BST

Algorithm

We know that the Inorder traversal of a Binary Search Tree(BST) is a sorted order of elements present in the tree. Hence we can do the inorder traversal of the above tree and store it in an array. Later we can check if the generated array is sorted or not.

This approach will run in O(N) time, but the space complexity of the above approach is also O(N), because of the additional array.

Space optimized approach

In the above approach, the generated array is actually unnecessary except for comparing if the current element is greater than the previous element.

Hence instead of storing all the elements in an array, we will keep track of previous element data value and check if the value of the current node is greater than the previous element or not.

If the current node value is greater than the previous element for all the elements, then it’s a valid BST, else it is not a valid BST.

valid_bst(tree, prev)
{
	if(tree == NULL)
	    return true;

	if(!valid_bst(tree->left, prev))
	    return false;
	//if current element is less than previous node
       // in inorder traversal than it is not a valid BST
	if(tree->data < prev) 
            return false; 

        prev = tree->data;
	if(!valid_bst(tree->right, prev))
	    return false;

	return true;
}

Implementation of the above algorithm in CPP

#include <bits/stdc++.h>
using namespace std;

class Node{
    public:
        int data;
        Node *left;
        Node *right;

    public:
        Node(int x){
            data = x;
            left = NULL;
            right = NULL;
        }
};

bool valid_bst(Node *tree, int *prev)
{
    if(tree == NULL)
        return true;

    if(!valid_bst(tree->left, prev))
        return false;
    
    if(tree->data < *prev)
        return false;
    
    
    *prev = tree->data;
    if(!valid_bst(tree->right, prev))
        return false;


    return true;
}

int main()
{
    Node *tree = new Node(15);
    tree->left = new Node(8);
    tree->right = new Node(25);
    tree->left->left = new Node(4);
    tree->left->right = new Node(12);
    tree->right->left = new Node(20);
    tree->right->right = new Node(30);

    int prev = 0;
    int res = valid_bst(tree, &prev);

    if(res == 0)
        cout<<"false"<<endl;
    else
        cout<<"true"<<endl;
}
Output
Input:
          15
        /    \
      8       25
    /  \     /  \
   4   12   20   30

Output:
true

Time Complexity

The time complexity of the above algorithm is O(N), where N is the number of nodes a given tree because we are going to traverse all the elements of a given tree to check if the tree is valid Binary Search Tree. The space complexity of the above algorithm is O(1) as we are strong only a previous node value in an integer variable.

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here