Site icon

Check given binary tree is binary search tree (java/ recursive/ examples)

Fig 1: Check binary tree is BST

Algorithm: check given binary tree is binary search tree in java

Optimized algorithm to check given binary tree is binary search tree

Examples: check binary tree is binary search tree using recursive algorithm

Example 1: Check given binary tree is binary search tree

Fig 2: Value at every non leaf node

The above binary tree is binary search tree, as every node within its specified range.

Example 2: Given binary tree is not binary search tree.

Fig 3: Binary tree not BST

Time Complexity of algorithm is O(n).

Program – Check given binary tree is binary search tree in java

1.) IsBST Class:

package org.learn.Question;

import org.learn.PrepareTree.Node;

public class IsBST {
	public static boolean isBST(Node node) {
		return IsBST.isBST(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}

	private static boolean isBST(Node node, int min, int max) {
		if (node == null)
			return true;

		if (node.data < min || node.data > max)
			return false;

		boolean isLeft = isBST(node.left, min, node.data);
		if (!isLeft)
			return isLeft;

		boolean isRight = isBST(node.right, node.data, max);
		if (!isRight)
			return isRight;

		return true;
	}
}

2.) Node Class:

package org.learn.PrepareTree;

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

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App class:

package org.learn.Client;

import org.learn.PrepareTree.Node;
import org.learn.Question.IsBST;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
       Node J = Node.createNode(160);
       Node K = Node.createNode(190);
             
       //connect Level 0 and 1
       A.left  = B;
       A.right = C;
       //connect level 1 and level 2
       B.left  = D;
       B.right = E;
       C.left  = F;
       C.right = G;
       //Connect level 2 and level 3
       F.left  = H;
       F.right = I;
       G.left  = J;
       G.right = K;
         
       if(IsBST.isBST(A)) {
    	   System.out.println("Binary Tree is binary search tree");;
       } else {
    	   System.out.println("Binary Tree is not binary search tree");
       }
       
       Node H1 = Node.createNode(90);
       F.left  = H1;
       if(IsBST.isBST(A)) {
    	   System.out.println("Binary Tree is binary search tree");;
       } else {
    	   System.out.println("Binary Tree is not binary search tree");
       }
    }
}

Output – check given binary tree is BST in java (Fig 2 & Fig 3)

Binary Tree is binary search tree
Binary Tree is not binary search tree

Download  code – Check binary tree is binary search tree recursive algorithm

Exit mobile version