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.

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.

**public class**BinarySearchTree {- public static class Node{
- int data;
- Node left;
- Node right;
- public Node(int data){
- this.data = data;
- left = right = null;
- }
- }
- //Method overloading
- public boolean checkIfBinarySearchTree(Node root) {
- if (true) {
- return checkIfBinarySearchTree(root, null, null);
- }
- return false;
- }
- public boolean checkIfBinarySearchTree(Node root, Integer max, Integer min) {
- if (root == null) return true;
- if (max != null && root.data >= max) return false;
- if (min != null && root.data <= min ) return false;
- return checkIfBinarySearchTree(root.left, root.data, min) &&
- checkIfBinarySearchTree(root.right, max, root.data);
- }
- }

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

- public class BinarySearchTreeMain {
- public static void main(String[] args) {
- BinarySearchTree binarySearchTree = new BinarySearchTree();
- BinarySearchTree.Node root;
- root = new BinarySearchTree.Node(10);
- root.left = new BinarySearchTree.Node(5);
- root.right = new BinarySearchTree.Node(15);
- root.left.left = new BinarySearchTree.Node(2);
- root.left.right = new BinarySearchTree.Node(7);
- root.right.left = new BinarySearchTree.Node(13);
- root.right.right = new BinarySearchTree.Node(26);
- System.out.println("The first check : " + binarySearchTree.checkIfBinarySearchTree(root));
- root = new BinarySearchTree.Node(10);
- root.left = new BinarySearchTree.Node(5);
- root.right = new BinarySearchTree.Node(15);
- root.left.left = new BinarySearchTree.Node(2);
- root.left.right = new BinarySearchTree.Node(7);
- root.right.left = new BinarySearchTree.Node(13);
- root.right.right = new BinarySearchTree.Node(11);
- System.out.println("The second check : " + binarySearchTree.checkIfBinarySearchTree(root));
- }
- }

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
```

**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.

**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)

Interesting problem, thanks for sharing

ReplyDelete