Binary search tree in java

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.
Search node in Binary search tree



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.
Insert node in binary search tree

Complete java program:

package org.arpit.java2blog;

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 

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012