How to check if a given Tree is a Binary Search Tree in Java? Example Tutorial

Hello guys, if you are preparing for a coding interview then you may know those binary tree problems are not easy to solve on coding interviews and I have seen many candidates struggling to do post-order traversal and checking if a given binary tree is a binary search tree or not. If you want to succeed in the coding interview, you need to prepare well on binary trees in general. One way to prepare better is solving common binary tree coding problems like this one, where you need to find if the given tree is BST or not. There are a lot of things that would tell us if a tree is a binary search tree. But before we get to that, we need to understand what a binary tree is.

A Binary tree is a data structure in which each node can have at most two children. That is, each node in the binary tree will have data, left child and right child. The first node of the tree is called the Root.

Below is the image of a binary search tree, all the green circles are called nodes and they have at most two other nodes called children.

Fig 1.0 Binary Tree.

In the diagram above, The root node is node 8 as you can see, And it has two Children node 3 and node 10, left and right respectively. Node 3 also has two children nodes 1 and 6. Node 6 has two children, node 4 and node 7 respectively,

And to the right side of node 8 which is node 10, has just only one child, node 14, and it as well has only one child. Nodes 4, 7, and 13 are called leaves because they do not have children.

How to find if a given tree is a binary search tree or not?

There are some important things to note when determining is if a tree is a binary search tree or not, which are :

ü All data in the nodes of the left sub-tree are lesser than the right.

ü In the Children nodes, All data on the left are lesser than the right.

ü All data in the nodes of the left sub-tree is lesser than the root

ü All data in the nodes of the right sub-tree is greater than the root.

So, with all these bullet points listed above, you can determine if a tree is a binary tree or not. 

A Binary search tree (I.e BST) is a type of binary tree. It can also be defined as a node-based binary tree. BST is also referred to as ‘Ordered Binary Tree’. The BST data structure is considered to be very efficient when compared to Arrays and Linked lists when it comes to insertion/deletion and searching of items.

BST takes O (log n) time to search for an element. As elements are ordered, half the sub-tree is discarded at every step while searching for an element. This becomes possible because we can easily determine the rough location of the element to be searched.

Similarly, insertion and deletion operations are more efficient in BST. When we want to insert a new element, we roughly know in which subtree (left or right) we will insert the element

Java Program to check if the given Binary tree is BST or not? Example

Now, we shall be doing a task and see a coding example to find out whether a given binary tree is a binary search tree or not for better understanding.

1. public class BinarySearchTree {
2. public static class Node{
3. int data;
4. Node left;
5. Node right;
6. public Node(int data){
7. this.data = data;
8. left = right = null;
9. }
10. }
11. //Method overloading
12. public boolean checkIfBinarySearchTree(Node root) {
13. if (true) {
14. return checkIfBinarySearchTree(root, null, null);
15. }
16. return false;
17. }
18. public boolean checkIfBinarySearchTree(Node root, Integer max, Integer min) {
19. if (root == null) return true;
20. if (max != null && root.data >= max) return false;
21. if (min != null && root.data <= min ) return false;
22. return checkIfBinarySearchTree(root.left, root.data, min) &&
23. checkIfBinarySearchTree(root.right, max, root.data);
24. }
25. }

 The class for the main method goes thus(i.e Driver class):

1. public class BinarySearchTreeMain {
2. public static void main(String[] args) {
3. BinarySearchTree binarySearchTree = new BinarySearchTree();
4. BinarySearchTree.Node root;
5. root = new BinarySearchTree.Node(10);
6. root.left = new BinarySearchTree.Node(5);
7. root.right = new BinarySearchTree.Node(15);
8. root.left.left = new BinarySearchTree.Node(2);
9. root.left.right = new BinarySearchTree.Node(7);
10. root.right.left = new BinarySearchTree.Node(13);
11. root.right.right = new BinarySearchTree.Node(26);
12. System.out.println("The first check : " + binarySearchTree.checkIfBinarySearchTree(root));
13. root = new BinarySearchTree.Node(10);
14. root.left = new BinarySearchTree.Node(5);
15. root.right = new BinarySearchTree.Node(15);
16. root.left.left = new BinarySearchTree.Node(2);
17. root.left.right = new BinarySearchTree.Node(7);
18. root.right.left = new BinarySearchTree.Node(13);
19. root.right.right = new BinarySearchTree.Node(11);
20. System.out.println("The second check : " + binarySearchTree.checkIfBinarySearchTree(root));
21. }
22. }

From the first class in Line 1 to 10 of the first codes, there are two classes embedded there, the class “Node” in the class “Binary search tree” line 6 is the constructor initializing the class “Node”. In line 12 there is a method “ checkIfBinarySearchTree” that calls another method of the same name too but of different signatures - Method overloading.

The method in line 12 takes in one parameter(root) of type Node. And the other takes in 3 parameters, which are the root, min, and max. The method in line 18 checks if the root is null, it should return true in line 19, if the max is not null and the data in the root node is greater than or equal to max it should return false in line 20, if the min is not null and the data in the root node is lesser or equal to min, it should return false in line 21.

Line 22 and 23 returns a recursive call with the appropriate parameters

In the driver class, which is the main method. Line 3 creates an instance of the class “BinarySearchTree” while line 4 is creating a variable “root” of type“BinarySearchTree.Node”. Line 7 to 11 initializes the nodes right from the root node down to its children and grandchildren. If you’ve understood the concept of a binary tree, you know the first is a binary tree, and the second from lines 13-19 is not.

How?

Check line10-11 and 18-19 to see the difference. In line 19, The right node of the root(I.e, root.right.right) was set to 11 and it is lesser to its left in line 18 which is wrong because all right nodes are greater than the root

Output

The first check: true

The second check: false

That's all about how to check if a given tree is a binary search tree in Java or not. This is a common coding problem and is often asked by beginners to check their knowledge of hierarchical data structure and binary search trees. Remembering the binary search tree properties or criteria is the key to solving this problem so make sure you revise binary tree theory before you go for any coding interview.

 

Other binary tree and data structure tutorials you may like to explore

• 5 data structure and algorithm books for coding interviews (list)
• How to implement pre-order traversal in Java?  (solution)
• How to print all leaf nodes of a binary tree without recursion in Java? (solution)
• How to implement linked lists using generic in Java? (solution)
• 10 Free Data Structure and Algorithms Courses (courses)
• Write a program to find the missing number in an integer array of 1 to 100? [solution]
• How do you reverse an array in place in Java? [solution]
• 50+ Data Structure and Algorithms Coding Problems from Interviews (questions)
• 10 Algorithms Books Every Programmer should read [books]
• How to implement in-order traversal in Java? (solution)
• How to print all leaf nodes of a binary tree in Java? (solution)
• 30+ Array-based Coding Problems from Interviews (questions)
• How to implement in-order traversal in Java without recursion? (solution)
• How to traverse a binary tree in pre-order without using recursion? (solution)
• How to check if an array contains a number in Java? [solution]
• 10 Algorithms courses to Crack Coding Interviews [courses]
• How to find the middle element of a linked list using a single pass? (solution)
• How to reverse a singly linked list in Java? (solution)
• How to find the 3rd element from the end of the linked list in Java? (solution)
• How to reverse an array in place in Java? (solution)
• How to print duplicate elements of an array in Java? (solution)

Thanks for reading this article. If you like these binary tree questions and my explanation then please share them with your friends and colleagues. If you have any questions or feedback then please drop a comment. 

P. S. - If you are looking for free data structure courses to learn binary tree concepts better then you can also check out this list of best free data structure and algorithms courses for Java and C programmer. This article contains the best free algorithms courses from Udemy and Pluralsight for Java developers.