Easy methods to examine if a given Tree is a Binary Search Tree in Java? Instance Tutorial

Under
is the picture of a binary search tree, all of the inexperienced circles are known as
nodes and so they have at most two different nodes known as youngsters.

Fig 1.0 Binary Tree.

Within the diagram above, The foundation node is node 8 as you may see, And it has two Kids node 3 and node 10, left and proper respectively. Node 3 additionally has two youngsters nodes 1 and 6. Node 6 has two youngsters, node 4 and node 7 respectively,

And to the precise facet of node 8 which is node 10, has simply just one baby, node 14, and it as nicely has just one baby. Nodes 4, 7, and 13 are known as leaves as a result of they don’t have youngsters.

Easy methods to discover if a given tree is a binary search tree or not?

There are some vital issues to notice when figuring out is that if a tree is a binary search tree or not, that are :

ü All knowledge within the nodes of the left sub-tree are lesser than the precise.

ü Within the Kids nodes, All knowledge on the left are lesser than the precise.

ü All knowledge within the nodes of the left sub-tree is lesser than the basis

ü All knowledge within the nodes of the precise sub-tree is larger than the basis.

So, with all these bullet factors listed above, you may decide if a tree is a binary tree or not. 

A Binary search tree (I.e BST) is a sort of binary tree. It can be outlined as a node-based binary tree. BST can be known as ‘Ordered Binary Tree’. The
BST knowledge construction is taken into account to be very environment friendly when in comparison with
Arrays and Linked lists in the case of insertion/deletion and
looking of things.

BST takes O (log n) time to seek for a component. As parts are ordered, half the sub–tree
is discarded at each step whereas trying to find a component. This turns into
doable as a result of we will simply decide the tough location of the
ingredient to be searched.

Equally,
insertion and deletion operations are extra environment friendly in BST. Once we
need to insert a brand new ingredient, we roughly know through which subtree (left or proper) we are going to insert the ingredient

Java Program to examine if the given Binary tree is BST or not? Instance

Now, we will be doing a process and see a coding instance to search out out whether or not a given binary tree is a binary search tree or not for higher understanding.

1. public class BinarySearchTree {

2. public static class Node{

3. int knowledge;

4. Node left;

5. Node proper;

6. public Node(int knowledge){

7. this.knowledge = knowledge;

8. left = proper = null;

9. }

10. }

11. //Methodology 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.knowledge >= max) return false;

21. if (min != null && root.knowledge <= min ) return false;

22. return checkIfBinarySearchTree(root.left, root.knowledge, min) &&

23. checkIfBinarySearchTree(root.proper, max, root.knowledge);

24. }

25. }

 The category for the primary technique goes thus(i.e Driver class):

1. public class BinarySearchTreeMain {

2. public static void principal(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.proper = new BinarySearchTree.Node(15);

8. root.left.left = new BinarySearchTree.Node(2);

9. root.left.proper = new BinarySearchTree.Node(7);

10. root.proper.left = new BinarySearchTree.Node(13);

11. root.proper.proper = new BinarySearchTree.Node(26);

12. System.out.println(“The primary examine : “
    + binarySearchTree.checkIfBinarySearchTree(root));

13. root = new BinarySearchTree.Node(10);

14. root.left = new BinarySearchTree.Node(5);

15. root.proper = new BinarySearchTree.Node(15);

16. root.left.left = new BinarySearchTree.Node(2);

17. root.left.proper = new BinarySearchTree.Node(7);

18. root.proper.left = new BinarySearchTree.Node(13);

19. root.proper.proper = new BinarySearchTree.Node(11);

20. System.out.println(“The second examine : “
    + binarySearchTree.checkIfBinarySearchTree(root));

21. }

22. }

From
the primary class in Line 1 to 10 of the primary codes, there are two
courses embedded there, the category “Node” within the class “Binary search
tree” line 6 is the constructor initializing the category “Node”. In line
12 there’s a technique “ checkIfBinarySearchTree” that calls one other technique of the identical title too however of various signatures – Methodology overloading. 

The technique in line 12 takes in a single parameter(root) of sort Node. And the opposite takes in 3 parameters, that are the basis, min, and max. The
technique in line 18 checks if the basis is null, it ought to return true in
line 19, if the max isn’t null and the info within the root node is larger
than or equal to max it ought to return false in line 20, if the min is
not null and the info within the root node is lesser or equal to min, it
ought to return false in line 21.

Line 22 and 23 returns a recursive name with the suitable parameters

Within the driver class, which is the primary technique. Line 3 creates an occasion of the category “BinarySearchTree” whereas line 4 is making a variable “root” of sort“BinarySearchTree.Node”. Line 7 to 11 initializes the nodes proper from the basis node all the way down to its youngsters and grandchildren. If you’ve understood the idea of a binary tree, you understand the primary is a binary tree, and the second from strains 13-19 isn’t.

How?

Check line10-11 and 18-19 to see the distinction. In
line 19, The appropriate node of the basis(I.e, root.proper.proper) was set to
11 and it’s lesser to its left in line 18 which is mistaken as a result of all
proper nodes are better than the basis

Output

The primary examine: true

The second examine: false

That is all about the best way to examine if a given tree is a binary search tree in Java or not. It is a widespread coding drawback and is commonly requested by newcomers to examine their data of hierarchical knowledge construction and binary search bushes. Remembering the binary search tree properties or standards is the important thing to fixing this drawback so ensure you revise binary tree idea earlier than you go for any coding interview.