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.
The class for the main method goes thus(i.e Driver class):
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.
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.
- 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)