Binary Search In Java With Example

Binary Search Tree :

A common type of binary tree is a binary search tree, in which every node has a value that is greater than or equal to the node values in the left sub-tree, and less than or equal to the node values in the right sub-tree.

This is a Java Program to implement Binary Search Tree. A binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree must each also be a binary search tree
• There must be no duplicate nodes.

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right subtree of the root node should be greater than the data of the root.

---

Example of Binary Search

Output :

 inserted: 10
[input: 20] ->10 [R] -> inserted: 20
[input: 21] ->10 [R] ->20 [R] -> inserted: 21
[input: 8] ->10 [L] -> inserted: 8
[input: 6] ->10 [L] ->8 [L] -> inserted: 6
[input: 16] ->10 [R] ->20 [L] -> inserted: 16
[input: 23] ->10 [R] ->20 [R] ->21 [R] -> inserted: 23

Exmaple 2:

Output :

Element is found at index: 2