Check for BST

Problem Statement

Given a binary tree, we have to determine if the tree is a binary search tree or not.
A tree is said to be a valid binary search tree when,

• All the nodes in the left subtree are less than the parent node
• All the nodes in the right subtree are greater than the parent node.
• Also, the left and right subtrees have to satisfy the binary search tree conditions.

Example

consider the following examples
example-1

                3
               / \
              2   5
             / \   \
            1   4   6

output:

Not a binary search tree

example-2

                4
               / \
              2   5
             / \   \
            1   3   6

output:

Valid binary search tree

Example Explanation

In example 1,
Condition 1 is not satisfied. All the nodes in the left subtree have to be less than the parent node, but 4 is not less than 3. Hence, it’s not a binary search tree

In example 2,
Condition 1 is satisfied, where all the nodes in the left subtree are less than the parent node. Similarly, condition 2 is satisfied, where all the nodes in the right subtree are greater than the parent node. And condition 3 is satisfied, where both left and right subtrees have fulfilled the bst conditions.

Constraints

The constraints we are going to follow for the below implementations are,

• Given tree can have any number of edges between $0$ and $10000$ (both inclusive).
• Each node can have any value between $-2^{31}$ and $2^{31}-1$ (both inclusive).

Approach 1- Brute Force Approach

The idea is to check if all the nodes in the left subtree are less than the parent node and if all the nodes in the right subtree are greater than the parent node for all the nodes in the tree.

Now instead of checking for all nodes in the left and right subtrees, we can compare the parent node with max in the left subtree, and min in the right subtree.

Algorithm

The algorithm to check for the bst follows as
for each node in the tree,

• Find the max of all the nodes in the left subtree, and check if the max is less than the current node.
• Find the min of all the nodes in the right subtree, and check if the min is greater than the current node.
• Validate if both left and right subtrees satisfy the bst conditions.

Code Implementation

The java implementation of brute force approach to check for bst follows as

class Tree{
    //contents of each tree node
    int val;
    Tree left;
    Tree right;

    //tree class constructor
    Tree(int val){
        this.val = val;
        left=null;
        right=null;
    }

}

public class Main{

    //method to check if tree is bst
    public boolean isBst(Tree root){
        //base case
        if(root == null)
            return true;

        //fetch the max of all nodes in the left subtree
        int max = getMax(root.left);
        /*
        condition 1, check if all nodes in left subtree
        are less than the parent node
        */
        if(max >= root.val)
            return false;

        //fetch the min of all nodes in the right subtree
        int min = getMin(root.right);
        /*
        condition 2, check if all nodes in right subtree
        are greater than the parent node
        */
        if(min <= root.val)
            return false;

        /*
        condition 3, check if both the left and right subtree
        satisfy the bst conditions
        */
        if((!isBst(root.left)) || (!isBst(root.right)))
            return false;

        return true;
    }

    public int getMax(Tree root){//method to fetch the max of given tree
        //base case
        if(root == null)
            return Integer.MIN_VALUE;

        int leftMax = getMax(root.left);
        int rightMax = getMax(root.right);

        return Math.max(root.val, Math.max(leftMax, rightMax));
    }

    public int getMin(Tree root){//method to fetch the min of given tree
        //base case    
        if(root == null)
            return Integer.MAX_VALUE;

        int leftMin = getMin(root.left);
        int rightMin = getMin(root.right);

        return Math.min(root.val, Math.min(leftMin, rightMin));
    }

    public static void main(String[] args) {
        Tree root = new Tree(4);
        root.left = new Tree(2);
        root.right = new Tree(5);
        root.left.left = new Tree(1);
        root.left.right = new Tree(3);
        root.right.right = new Tree(6);

        Main m = new Main();
        if(m.isBst(root)){
            System.out.println("Given tree is a valid bst");
        }
        else{
            System.out.println("Given tree is not a bst");
        }
    }
}

Output:

Given tree is a valid bst

C++ implementation of brute force approach to check for bst follows as

#include<iostream>
#include<climits>

using namespace std;

struct Tree{
    //contents of each tree node
    int val;
    Tree* left;
    Tree* right;

};

//method to initialize new tree node
Tree* newNode(int val){

    Tree* node = new Tree;
    node->val = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}

int getMax(Tree* root){//method to fetch the max of given tree
    //base case
    if(root == NULL)
        return INT_MIN;

    int leftMax = getMax(root->left);
    int rightMax = getMax(root->right);

    int res = leftMax>rightMax?leftMax:rightMax;

    return res>root->val?res:root->val;
}

int getMin(Tree* root){//method to fetch the min of given tree
    //base case
    if(root == NULL)
        return INT_MAX;

    int leftMin = getMin(root->left);
    int rightMin = getMin(root->right);

    int res = leftMin<rightMin?leftMin:rightMin;

    return res<root->val?res:root->val;
}

bool isBst(Tree* root){
    //base case
    if(root == NULL)
        return true;

    //fetch the max of all nodes in the left subtree
    int max = getMax(root->left);
    /*
    condition 1, check if all nodes in left subtree
    are less than the parent node
    */
    if(max >= root->val)
        return false;

    //fetch the min of all nodes in the right subtree
    int min = getMin(root->right);
    /*
    condition 2, check if all nodes in right subtree
    are greater than the parent node
    */
    if(min <= root->val)
        return false;

    /*
    condition 3, check if both the left and right subtree
    satisfy the bst conditions
    */
    if((!isBst(root->left)) || (!isBst(root->right)))
        return false;

    return true;
}

int main() {
    Tree* root = newNode(3);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(4);
    root->right->right = newNode(6);

    if(isBst(root)){
        cout<<"Given tree is a valid bst";
    }
    else{
        cout<<"Given tree is not a bst";
    }
}

Output:

Given tree is not a bst

Python implementation of brute force approach to check for bst follows as

import sys

#contents of a tree node
class Tree:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val


def getMax(root):#method to fetch the max of given tree
    #base case
    if(root == None):
        return -sys.maxsize-1

    leftMax = getMax(root.left)
    rightMax = getMax(root.right)


    return max(root.val,max(leftMax,rightMax))


def getMin(root):#method to fetch the min of given tree
    #base case
    if(root == None):
        return sys.maxsize

    leftMin = getMin(root.left)
    rightMin = getMin(root.right)


    return min(root.val, min(leftMin, rightMin))


def isBst(root):
    #base case
    if(root == None):
        return True

    #fetch the max of all nodes in the left subtree
    max = getMax(root.left)
    '''
    condition 1, check if all nodes in left subtree
    are less than the parent node
    '''
    if(max >= root.val):
        return False

    #fetch the min of all nodes in the right subtree
    min = getMin(root.right)
    '''
    condition 2, check if all nodes in right subtree
    are greater than the parent node
    '''
    if(min <= root.val):
        return False

    '''
    condition 3, check if both the left and right subtree
    satisfy the bst conditions
    '''
    if((not isBst(root.left)) or (not isBst(root.right))):
        return False

    return True

#Driver code
root = Tree(3);
root.left = Tree(2);
root.right = Tree(5);
root.left.left = Tree(1);
root.left.right = Tree(4);
root.right.right = Tree(6);

if(isBst(root)):
    print("Given tree is a valid bst")

else:
    print("Given tree is not a bst")

Output:

Given tree is not a bst

Time Complexity

For each node, we are fetching the maximum of the left subtree and the minimum of the right subtree. The time required to find the minimum or maximum of a tree is O(N). Since we are doing it for each node and fetching both minimum and maximum, the time complexity will be N*O(N+N) i.e., O(N^2).

Space Complexity

This approach doesn’t use any auxiliary space, but it internally maintains a recursion stack of size H(height of tree) for checking bst and getting min functions. So the space complexity will be O(H).

Approach 2 – Using Upper and Lower Limits

The idea is to remove the getMin and getMax methods by adding lower and upper limit parameters in the function and check if the current node falls under the expected range. And one of the boundaries of the range gets narrowed in the further recursive calls to validate if the left and right subtrees satisfy the bst conditions.

Algorithm

The algorithm for the recursive approach follows as

• Add the parameters left and right along with root in the function.
• Check if the current node value falls between left and right.
• Traverse to left subtree by updating the right boundary to current node value.
• Traverse to right subtree by updating the left boundary to current node value.

Implementation

The java implementation for the above approach to check for bst follows as

class Tree{
    //contents of each tree node
    int val;
    Tree left;
    Tree right;

    //tree class constructor
    Tree(int val){
        this.val = val;
        left=null;
        right=null;
    }

}

public class Main{

    //method to check if tree is bst
    public boolean IsBst(Tree root, int minValue, int maxValue){
        //base case
        if(root == null)
            return true;

        //check if current value is greater than left boundary
        if(root.val<=minValue)
            return false;

        //check if currernt value is less right boundary
        if(root.val>=maxValue)
            return false;

        /*
        traverse to left subtree by narrowing the right boundary
        and traverse to right subtree by narrowing the left boundary
        */
        if(!IsBst(root.left, minValue, root.val) || !IsBst(root.right, root.val, maxValue))
            return false;

        return true;
    }


    public static void main(String[] args) {
        Tree root = new Tree(4);
        root.left = new Tree(2);
        root.right = new Tree(5);
        root.left.left = new Tree(1);
        root.left.right = new Tree(3);
        root.right.right = new Tree(6);

        Main m = new Main();

        if(m.IsBst(root, Integer.MIN_VALUE, Integer.MAX_VALUE)){
            System.out.println("Given tree is a valid bst");
        }
        else{
            System.out.println("Given tree is not a bst");
        }
    }
}

C++ implementation for the above approach to check for bst follows as

#include<iostream>
#include<climits>

using namespace std;

struct Tree{
    //contents of each tree node
    int val;
    Tree* left;
    Tree* right;

};

//method to initialize new tree node
Tree* newNode(int val){

    Tree* node = new Tree;
    node->val = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}

//method to check if tree is bst
bool IsBst(Tree* root, int minValue, int maxValue){
    //base case
    if(root == NULL)
        return true;

    //check if current value is greater than left boundary
    if(root->val<=minValue)
        return false;

    //check if currernt value is less than right boundary
    if(root->val>=maxValue)
        return false;

    /*
    traverse to left subtree by narrowing the right boundary
    and traverse to right subtree by narrowing the left boundary
    */
    if(!IsBst(root->left, minValue, root->val) || !IsBst(root->right, root->val, maxValue))
        return false;

    return true;
}

int main() {
    Tree* root = newNode(4);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(3);
    root->right->right = newNode(6);

    if(IsBst(root, INT_MIN, INT_MAX)){
        cout<<"Given tree is a valid bst";
    }
    else{
        cout<<"Given tree is not a bst";
    }
}

Python implementation for the above approach to check for bst follows as

import sys

#contents of a tree node
class Tree:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val


#method to check if tree is bst
def IsBst(root, minValue, maxValue):
    #base case
    if(root == None):
        return True

    #check if current value is greater than left boundary
    if(root.val<=minValue):
        return False

    #check if currernt value is less than right boundary
    if(root.val>=maxValue):
        return False

    '''
    traverse to left subtree by narrowing the right boundary
    and traverse to right subtree by narrowing the left boundary
    '''
    if(not IsBst(root.left, minValue, root.val) or not IsBst(root.right, root.val, maxValue)):
        return False

    return True

#Driver code
root = Tree(4);
root.left = Tree(2);
root.right = Tree(5);
root.left.left = Tree(1);
root.left.right = Tree(3);
root.right.right = Tree(6);

if(IsBst(root, -sys.maxsize-1, sys.maxsize)):
    print("Given tree is a valid bst")

else:
    print("Given tree is not a bst")

Output:

Given tree is a valid bst

Time Complexity

This approach has to visit each node in the tree and validate if the value falls under the expected range. So the time complexity will be O(N).

Space Complexity

This approach doesn’t require any auxiliary space, but it internally maintains a recursion stack of size H(height of binary tree). So the space complexity will be O(H).

Approach 3 – Using Inorder Traversal

One of the interesting properties of a binary search tree is that if we flatten the tree or consider the inorder traversal of the tree, the series will be in ascending order. Now one of the ways is to perform inorder traversal and check if the obtained array is sorted or not. But we can validate this during the inorder traversal itself.

The idea is to maintain a prev pointer and check if the next node in the inorder traversal is greater than the prev node or not.

Algorithm

The algorithm for the recursive inorder approach follows as

• Maintain a prev node and initialize it with NULL.
• Perform a recursive inorder traversal.
• If prev is NULL, update it to current.
• If prev is not NULL, validate if the current node is larger than prev.
• Update the prev to current.

Similarly, the algorithm for the iterative inorder approach follows as

• Maintain a prev node, initialize it with NULL and maintain a stack for inorder traversal.
• Perform an iterative inorder traversal.
• If prev is NULL, update it to current.
• If prev is not NULL, validate if the current node is larger than prev.
• Update the prev to current.

Implementation

The java implementation for the inorder approach to check for bst follows as

import java.util.*;
class Tree{
    //contents of each tree node
    int val;
    Tree left;
    Tree right;

    //tree class constructor
    Tree(int val){
        this.val = val;
        left=null;
        right=null;
    }

}

public class Main{

    Tree prev;

    //modified inorder traversal,
    //which compares current node with previous nodes
    public boolean modifiedInorder(Tree root){
        //base case
        if(root == null)
            return true;

        //traverse the left subtree
        if(!modifiedInorder(root.left))
            return false;

        //if prev is null update it to root
        if(prev == null)
            prev=root;
        /*
        else compare the current with prev 
        and update the prev to current
        */
        else if(root.val<=prev.val)
            return false;
        else
            prev=root;

        //traverse the right subtree
        return modifiedInorder(root.right);
    }

    //method to check if tree is bst
    public boolean recursiveIsBst(Tree root){
        prev = null;
        return modifiedInorder(root);
    }

    public boolean iterativeIsBst(Tree root){
        Stack<Tree> s=new Stack<>();
        Tree previous = null;
        Tree curr = root;
        //modified iterative inorder traversal
        while(!s.isEmpty() || curr!=null){
            //traverse the left subtree
            if(curr!=null){
                s.push(curr);
                curr=curr.left;
                continue;
            }

            curr = s.peek();
            s.pop();

            /*
            if prev is null update it to curr
            else compare the current with prev 
            and update the prev to current
            */
            if(previous!=null && curr.val<=previous.val)
                return false;
            previous = curr;

            //traverse the right subtree
            curr=curr.right;
        }
        return true;
    }


    public static void main(String[] args) {
        Tree root = new Tree(4);
        root.left = new Tree(2);
        root.right = new Tree(5);
        root.left.left = new Tree(1);
        root.left.right = new Tree(3);
        root.right.right = new Tree(6);

        Main m = new Main();

        if(m.recursiveIsBst(root)){
            System.out.println("Given tree is a valid bst");
        }
        else{
            System.out.println("Given tree is not a bst");
        }

        if(m.iterativeIsBst(root)){
            System.out.println("Given tree is a valid bst");
        }
        else{
            System.out.println("Given tree is not a bst");
        }
    }
}

Output:

Given tree is a valid bst
Given tree is a valid bst

C++ implementation for the inorder approach to check for bst follows as

#include<iostream>
#include <stack>

using namespace std;

struct Tree{
    //contents of each tree node
    int val;
    Tree* left;
    Tree* right;

};

//method to initialize new tree node
Tree* newNode(int val){

    Tree* node = new Tree;
    node->val = val;
    node->left = NULL;
    node->right = NULL;

    return node;
}


//method to check if tree is bst
//modified inorder traversal,
//which compares current node with previous nodes
bool recursiveIsBst(Tree* root){
    static Tree* prev = NULL;
    //base case
    if(root == NULL)
        return true;

    //traverse the left subtree
    if(!recursiveIsBst(root->left))
        return false;

    //if prev is null update it to root
    if(prev == NULL)
        prev=root;
    /*
    else compare the current with prev 
    and update the prev to current
    */
    else if(root->val<=prev->val)
        return false;
    else
        prev=root;

    //traverse the right subtree
    return recursiveIsBst(root->right);
}

//iterative approach to check if tree is bst

bool iterativeIsBst(Tree* root){
    stack<Tree*> s;
    Tree* previous = NULL;
    Tree* curr = root;
    //modified iterative inorder traversal
    while(!s.empty() || curr!=NULL){
        //traverse the left subtree
        if(curr!=NULL){
            s.push(curr);
            curr=curr->left;
            continue;
        }

        curr = s.top();
        s.pop();

        /*
        if prev is null update it to curr
        else compare the current with prev 
        and update the prev to current
        */
        if(previous!=NULL && curr->val<=previous->val)
            return false;
        previous = curr;

        //traverse the right subtree
        curr=curr->right;
    }
    return true;
}

int main() {
    Tree* root = newNode(3);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(1);
    root->left->right = newNode(4);
    root->right->right = newNode(6);

    if(recursiveIsBst(root)){
        cout<<"Given tree is a valid bst \n";
    }
    else{
        cout<<"Given tree is not a bst \n";
    }

    if(iterativeIsBst(root)){
        cout<<"Given tree is a valid bst";
    }
    else{
        cout<<"Given tree is not a bst";
    }
}

Output:

Given tree is not a bst 
Given tree is not a bst

Python implementation for the inorder approach to check for bst follows as

#contents of a tree node
class Tree:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

prev=None

#modified inorder traversal,
#which compares current node with previous nodes
def modifiedInorder(root):
    global prev
    #base case
    if(root == None):
        return True

    #traverse the left subtree
    if(not modifiedInorder(root.left)):
        return False

    '''    
    if prev is null update it to root
    else compare the current with prev 
    and update the prev to current
    '''
    if(prev == None):
        prev=root
    elif(root.val<=prev.val):
        return False
    else:
        prev=root

    #traverse the right subtree
    return modifiedInorder(root.right)


#recurisve method to check if tree is bst
def recursiveIsBst(root):
    global prev
    prev = None
    return modifiedInorder(root)

#iterative method to check if tree is bst
def iterativeIsBst(root):
    stack = []
    previous = None
    curr = root
    #modified iterative inorder traversal
    while(stack or curr!=None):
        #traverse the left subtree
        if(curr!=None):
            stack.append(curr)
            curr=curr.left
            continue

        curr = stack.pop()

        '''
        if prev is null update it to curr
        else compare the current with prev 
        and update the prev to current
        '''
        if(previous!=None and curr.val<=previous.val):
            return False
        previous = curr

        #traverse the right subtree
        curr=curr.right
    return True

#Driver code
root = Tree(3);
root.left = Tree(2);
root.right = Tree(5);
root.left.left = Tree(1);
root.left.right = Tree(4);
root.right.right = Tree(6);

if(recursiveIsBst(root)):
    print("Given tree is a valid bst")

else:
    print("Given tree is not a bst")

if(iterativeIsBst(root)):
    print("Given tree is a valid bst")

else:
    print("Given tree is not a bst")

Output:

Given tree is not a bst
Given tree is not a bst

Time Complexity

In the recursive approach, we are visiting each node in the tree and compare it with the previous node. So the time complexity will be O(N).
Similarly, in the iterative approach, we are looping over the stack of size N, so the time complexity will be O(N).

Space Complexity

The recursive approach doesn’t require any auxiliary space, but it internally maintains a recursion stack of size H(height of tree) for inorder traversal. So the space complexity will be O(H).
The iterative approach uses an auxiliary stack for inorder traversal that at most go to size H(height of tree), so the space complexity will be O(H).

Conclusion

• A tree is a valid binary search tree when all the nodes in the left subtree are less than and all the nodes in the right subtree are larger than the parent node.
• Each subtree in a bst must also satisfy the bst conditions.
• The brute force approach to check for a bst is by comparing the current node with the max of the left subtree and the min of the right subtree. Time complexity is O(N^2), and space complexity is O(H).
• A little optimized approach is to set boundaries for a node value and validate if each node satisfies the boundaries. Time complexity is O(N), and space complexity is O(H).
• We can use inorder traversal to check if a tree is bst by maintaining a previous pointer and comparing it with the current. Time Complexity is O(N), and space complexity is O(H).
• Inorder approach to check for a BST is the best in terms of time and space.