Binary Search Tree in Java & Implementation

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Binary search tree is a special type of binary tree which have following properties.

Nodes which are smaller than root will be in left subtree.
Nodes which are greater than root will be right subtree.
It should not have duplicate nodes
Both left and right subtree also should be binary search tree.

Example of binary search tree:

Lets perform following operation on binary search tree

Find
Insert

Search()

Searching a node in binary search is very easy. You just need to traverse left (if smaller) and right (if greater) according to value to be found.

Algorithm:

If node to be found is equal to root, then search is successful
If node to be found is smaller than root , then traverse left subtree.
If node to be found is greater than root, then traverse right subtree
Repeat above steps recursively until you find the node.

Insert()

Insert node operation is also easy operation. You just need to compare it with root and traverse left (if smaller) or right(if greater) according to value of node to be inserted.

Algorithm:

Make root node as current node
If node to be inserted < root
- If it has left child then traverse left
- If it do not have left child, insert node here
If node to be inserted > root
- If it have right child, traverse right
- If it do not have right child, insert node here.

Complete java program:

100

101

package org.arpit.java2blog.binarysearchtree;

public class BinarySearchTreeMain {

public static class TreeNode

{

int data;

TreeNode left;

TreeNode right;

TreeNode(int data)

{

this.data=data;

}

public static boolean search(TreeNode root,TreeNode nodeToBeSearched)

{

if(root==null)

return false;

if(root.data== nodeToBeSearched.data)

{

return true;

}

boolean result=false;

if(root.data > nodeToBeSearched.data)

result=search(root.left,nodeToBeSearched);

else if(root.data < nodeToBeSearched.data)

result= search(root.right,nodeToBeSearched);

return result;

}

public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted)

{ if(root==null) {

root=nodeToBeInserted; return root;

} if(root.data > nodeToBeInserted.data)

{

if(root.left==null)

root.left=nodeToBeInserted;

else

insert(root.left,nodeToBeInserted);

}

else if(root.data < nodeToBeInserted.data)

if(root.right==null)

root.right=nodeToBeInserted;

else

insert(root.right,nodeToBeInserted);

return root;

}

public static void inOrder(TreeNode root)

{

if(root==null)

return;

inOrder(root.left);

System.out.print(root.data+" ");

inOrder(root.right);

}

public static void main(String[] args)

{

// Creating a binary search tree

TreeNode rootNode=createBinarySearchTree();

TreeNode node55=new TreeNode(55);

boolean result=search(rootNode,node55);

System.out.println("Searching for node 55 : "+result);

System.out.println("---------------------------");

TreeNode node13=new TreeNode(13);

TreeNode root=insert(rootNode,node13);

System.out.println("Inorder traversal of binary tree after adding 13:");

inOrder(root);

}

public static TreeNode createBinarySearchTree()

{

TreeNode rootNode =new TreeNode(40);

TreeNode node20=new TreeNode(20);

TreeNode node10=new TreeNode(10);

TreeNode node30=new TreeNode(30);

TreeNode node60=new TreeNode(60);

TreeNode node50=new TreeNode(50);

TreeNode node70=new TreeNode(70);

TreeNode node5=new TreeNode(5);

TreeNode node55=new TreeNode(55);

insert(null,rootNode);

insert(rootNode,node20);

insert(rootNode,node10);

insert(rootNode,node30);

insert(rootNode,node60);

insert(rootNode,node50);

insert(rootNode,node70);

insert(rootNode,node5);

insert(rootNode,node55);

return rootNode;

}

When you run above program, you will get below output:

Searching for node 55 : true

---------------------------

Inorder traversal of binary tree after adding 13:

5 10 13 20 30 40 50 55 60 70