Check if a binary tree is binary search tree or not in java

Table of Contents

First method:
- Java program:
Second Method:
- Java program:
Complete java program to check if Binary tree is binary search tree or not.

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post, we will see how to check if given binary tree is binary search tree or not. This is one of important interview questions on binary tree.
We will see two approaches to check if binary tree is bst or not.

First method:

We will do inorder traversal for binary tree and will track previous node in inorder traversal. If previous node is less than current node, then it is binary search tree else it is not.

Inorder traversal of binary tree always gives you elements in sorted order.

Java program:


public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
        /* base case: we reached null*/
        if (root == null) {
            return true;
        }

        if(!isBSTInOrder(root.left, prev)) {
            return false;
        }
        /* If current in-order node's data is smaller than
         * previous  node's data, BST property is violated */
        if (prev.data > root.data) {
            return false;
        }

        /* set the previous in-order data to the current node's data*/
        prev.data = root.data;

        return isBSTInOrder(root.right, prev);
    }

public static boolean isBSTInOrder(TreeNode root, TreeNode prev) {

/* base case: we reached null*/

if (root == null) {

return true;

}

if(!isBSTInOrder(root.left, prev)) {

return false;

}

/* If current in-order node's data is smaller than

* previous node's data, BST property is violated */

if (prev.data > root.data) {

return false;

}

/* set the previous in-order data to the current node's data*/

prev.data = root.data;

return isBSTInOrder(root.right, prev);

}

Second Method:

We will use min max range for a node. If node.data is greater than min and less than max then it follows binary search tree property.

When you traverse left, current node should be greater than min.
When you traverse right, current node should be less than max.
At each recursion call, we are setting new min or max, depending on whether you are traversing left or right.

Java program:


public static boolean isBST(TreeNode root, int min, int max) {

        /* base case: we reached null*/
        if(root == null) 
            return true;

        return (root.data > min &&
        root.data > max &&
        isBST(root.left, min, root.data) &&
        isBST(root.right, root.data, max));
    }

public static boolean isBST(TreeNode root, int min, int max) {

/* base case: we reached null*/

if(root == null)

return true;

return (root.data > min &&

root.data > max &&

isBST(root.left, min, root.data) &&

isBST(root.right, root.data, max));

}

Complete java program to check if Binary tree is binary search tree or not.


package org.arpit.java2blog.binarysearchtree;

import java.util.Stack;

public class BinarySearchTreeCheck {

    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

    // Recursive Solution
    public void inOrder(TreeNode root) {
        if(root !=  null) {
            inOrder(root.left);
            //Visit the node by Printing the node data  
            System.out.printf("%d ",root.data);
            inOrder(root.right);
        }
    }

    // Iterative solution
    public void inOrderIter(TreeNode root) {

        if(root == null)
            return;

        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode currentNode=root;

        while(!s.empty() || currentNode!=null){

            if(currentNode!=null)
            {
                s.push(currentNode);
                currentNode=currentNode.left;
            }
            else
            {
                TreeNode n=s.pop();
                System.out.printf("%d ",n.data);
                currentNode=n.right;
            }
        }
    }

    public static void main(String[] args)
    {
        // Creating a binary search tree
        TreeNode rootNode=createBinarySearchTree();

        System.out.println("-------------------------");
        System.out.println("Using inorder method");

        TreeNode prev=new TreeNode(Integer.MIN_VALUE);
        System.out.println(isBSTInOrder(rootNode,prev));

        System.out.println("-------------------------");
        System.out.println("Using min max method");
        System.out.println(isBST(rootNode,Integer.MIN_VALUE,Integer.MAX_VALUE));

        // Creating a binary tree which is not BST
        TreeNode rootNodeBinaryTree=createBinaryTree();

        System.out.println("-------------------------");
        System.out.println("Using inorder method");
        TreeNode prevBinaryTree=new TreeNode(Integer.MIN_VALUE);
        System.out.println(isBSTInOrder(rootNodeBinaryTree,prevBinaryTree));

        System.out.println("-------------------------");
        System.out.println("Using min max method");
        System.out.println(isBST(rootNodeBinaryTree,Integer.MIN_VALUE,Integer.MAX_VALUE));
        System.out.println("-------------------------");
    }

    public static TreeNode createBinarySearchTree()  
    {  

        TreeNode rootNode =new TreeNode(40);  
        TreeNode node20=new TreeNode(20);  
        TreeNode node10=new TreeNode(10);  
        TreeNode node30=new TreeNode(30);  
        TreeNode node60=new TreeNode(60);  
        TreeNode node50=new TreeNode(50);  
        TreeNode node70=new TreeNode(70);  
        TreeNode node5=new TreeNode(5);  
        TreeNode node55=new TreeNode(55);  

        rootNode.left=node20;  
        rootNode.right=node60;  

        node20.left=node10;  
        node20.right=node30;  

        node60.left=node50;  
        node60.right=node70;  

        node10.left=node5;  
        node50.right=node55;  
        return rootNode;  
    }  

    public static TreeNode createBinaryTree()  
    {  

        TreeNode rootNode =new TreeNode(40);  
        TreeNode node20=new TreeNode(20);  
        TreeNode node10=new TreeNode(10);  
        TreeNode node30=new TreeNode(30);  
        TreeNode node60=new TreeNode(60);  
        TreeNode node50=new TreeNode(50);  
        TreeNode node70=new TreeNode(70);  
        TreeNode node5=new TreeNode(5);  
        TreeNode node55=new TreeNode(55);  

        rootNode.left=node20;  
        rootNode.right=node10;  

        node20.left=node60;  
        node20.right=node30;  

        node60.left=node50;  
        node60.right=node70;  

        node10.left=node5;  
        node50.right=node55;  
        return rootNode;  
    }  

    public static boolean isBST(TreeNode root, int min, int max) {

        /* base case: we reached null*/
        if(root == null) 
            return true;

        return (root.data > min &&
        root.data > max &&
        isBST(root.left, min, root.data) &&
        isBST(root.right, root.data, max));
    }

    public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
        /* base case: we reached null*/
        if (root == null) {
            return true;
        }

        if(!isBSTInOrder(root.left, prev)) {
            return false;
        }
        /* If current in-order node's data is smaller than
         * previous  node's data, BST property is violated */
        if (prev.data > root.data) {
            return false;
        }

        /* set the previous in-order data to the current node's data*/
        prev.data = root.data;

        return isBSTInOrder(root.right, prev);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

package org.arpit.java2blog.binarysearchtree;

import java.util.Stack;

public class BinarySearchTreeCheck {

public static class TreeNode

{

int data;

TreeNode left;

TreeNode right;

TreeNode(int data)

{

this.data=data;

}

// Recursive Solution

public void inOrder(TreeNode root) {

if(root != null) {

inOrder(root.left);

//Visit the node by Printing the node data

System.out.printf("%d ",root.data);

inOrder(root.right);

}

// Iterative solution

public void inOrderIter(TreeNode root) {

if(root == null)

return;

Stack<TreeNode> s = new Stack<TreeNode>();

TreeNode currentNode=root;

while(!s.empty() || currentNode!=null){

if(currentNode!=null)

{

s.push(currentNode);

currentNode=currentNode.left;

}

else

{

TreeNode n=s.pop();

System.out.printf("%d ",n.data);

currentNode=n.right;

}

public static void main(String[] args)

{

// Creating a binary search tree

TreeNode rootNode=createBinarySearchTree();