Categories

# Binary Search Tree Program in Java

Binary Search Tree (BST in short) is a non-linear data structure. In this data structure, the data in each node N is greater than all the data in its left sub-tree, and the data is less than all the data in its right sub-tree.

The program below demonstrates some of the fundamental operations performed on binary search trees. The program includes insertion, deletion, searching, counting nodes, and traversal in inorder, preorder and postorder.

Traversal means visiting each node at least once in the given tree.

Preorder Traversal Steps:
1. Visit the root R.
2. Traverse the left sub-tree of R in preorder.
3. Traverse the right sub-tree of R in preorder.

Inorder Traversal Steps:
1. Traverse the left sub-tree of R in inorder.
2. Visit the root R.
3. Traverse the right sub-tree of R in inorder.

Postorder Traversal Steps:
1. Traverse the left sub-tree of R in postorder.
2. Traverse the right sub-tree of R in postorder.
3. Visit the root R.

``````import java.io.*;
class Node{
int data;
Node left;
Node right;
public Node(){
data = 0;
left = null;
right = null;
}
public Node(int d){
data = d;
left = null;
right = null;
}
}
class Tree{
Node root;
public Tree(){
root = null;
}
public boolean search(Node r, int d){
boolean found = false;
while(r != null && !found){
if(d < r.data){
r = r.left;
found = search(r, d);
}
else if(d > r.data){
r = r.right;
found = search(r, d);
}
else{
found = true;
break;
}
}
return found;
}
public Node insert(Node r, Node d){
if(r == null)
r = d;
else if(d.data < r.data)
r.left = insert(r.left, d);
else if(d.data > r.data)
r.right = insert(r.right, d);
return r;
}
public void preorder(Node r){
if(r != null){
System.out.print(r.data + "\t");
preorder(r.left);
preorder(r.right);
}
}
public void inorder(Node r){
if(r != null){
inorder(r.left);
System.out.print(r.data + "\t");
inorder(r.right);
}
}
public void postorder(Node r){
if(r != null){
postorder(r.left);
postorder(r.right);
System.out.print(r.data + "\t");
}
}
public int countNodes(Node r){
if(r == null)
return 0;
else{
int count = 1;
count += countNodes(r.left);
count += countNodes(r.right);
return count;
}
}
public Node delete(Node r, int d){
if(r == null)
return r;
if(d < r.data)
r.left = delete(r.left, d);
else if(d > r.data)
r.right = delete(r.right, d);
else{
if(r.left == null)
return r.right;
else if(r.right == null)
return r.left;
Node parent = r;
Node successor = r.right;
while(successor.left != null){
parent = successor;
successor = successor.left;
}
r.data = successor.data;
r.right = delete(r.right, r.data);
}
return r;
}
}
class BinarySearchTree{
public static void main(String args[])throws IOException{
Tree myTree = new Tree();
while(true){
System.out.println();
System.out.println("1. INSERT NODE");
System.out.println("2. SEARCH NODE");
System.out.println("3. PREORDER TRAVERSAL");
System.out.println("4. INORDER TRAVERSAL");
System.out.println("5. POSTORDER TRAVERSAL");
System.out.println("6. COUNT NODES");
System.out.println("7. DELETE NODE");
switch(choice){
case 1:
System.out.print("Data to be inserted: ");
Node n = new Node(d);
myTree.root = myTree.insert(myTree.root, n);
break;
case 2:
System.out.print("Data to be searched: ");
if(myTree.search(myTree.root, d))
System.out.println(d + " is available.");
else
System.out.println(d + " is unavailable.");
break;
case 3:
System.out.println("PREORDER TRAVERSAL:");
myTree.preorder(myTree.root);
break;
case 4:
System.out.println("INORDER TRAVERSAL:");
myTree.inorder(myTree.root);
break;
case 5:
System.out.println("POSTORDER TRAVERSAL:");
myTree.postorder(myTree.root);
break;
case 6:
int c = myTree.countNodes(myTree.root);
System.out.println("Number of nodes: " + c);
break;
case 7:
System.out.print("Data to be deleted: ");
boolean result = myTree.search(myTree.root, d);
if(!result){
System.out.println(d + " unavailable.");
break;
}
myTree.root = myTree.delete(myTree.root, d);
System.out.println(d + " deleted.");
break;
default:
System.out.println("Bye...");
return;
}
}
}
}``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.