Categories
Class 12

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{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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");
            System.out.print("Your choice: ");
            int choice = Integer.parseInt(br.readLine());
            switch(choice){
                case 1:
                System.out.print("Data to be inserted: ");
                int d = Integer.parseInt(br.readLine());
                Node n = new Node(d);
                myTree.root = myTree.insert(myTree.root, n);
                break;
                case 2:
                System.out.print("Data to be searched: ");
                d = Integer.parseInt(br.readLine());
                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: ");
                d = Integer.parseInt(br.readLine());
                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;
            }
        }
    }
}

Leave a Reply