Implementation of Binary Search Tree and its operations:

           Binary Search Tree is a special one in which the nodes are organised in sorted order.

It has following functions to implement.

• ‘Node creation’ -  Creates the structure of node
• ‘Class creation’ -class and its member functions are created.
• ‘Constrctor()’- initialises the values.
• ‘insert()’- add the node to the binary tree
• ‘insertRec()’ - add the elements to the tree.
• ‘inorder()’ -inorder traversal of node.
• ‘inorderRec()’ -inorder traversal of data.
• ‘search()’ -search the binary tree nodes
• ‘searchRec()’ – search the elements.
• ‘main()’ -it creates the object for class. It adds the elements, traverse the tree in inorder and find a key value.

Program:

import java.util.Scanner;

class Node {

    int key;

    Node l_value, r_value;

    public Node(int item) {

        key = item;

        l_value = r_value = null;

    }

}

class BinarySearchTreeEg {

    Node root;

     // Constructor to initialise values

    BinarySearchTreeEg() {

        root = null;

    }

     // Add a new key value

    void insert(int key) {

        root = insertRec(root, key);

    }

     // To insert a key using recursive function

    Node insertRec(Node root, int key) {

        if (root == null) {

            root = new Node(key);

            return root;

        }

        if (key < root.key) {

            root.l_value = insertRec(root.l_value, key);

        } else if (key > root.key) {

            root.r_value = insertRec(root.r_value, key);

        }

        return root;

    }

     // Let us do In-order traversal

    void inorder() {

        inorderRec(root);

    }

     void inorderRec(Node root) {

        if (root != null) {

            inorderRec(root.l_value);

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

            inorderRec(root.r_value);

        }

    }

     // let us search the key

    boolean search(int key) {

        return searchRec(root, key);

    }

     boolean searchRec(Node root, int key) {

        if (root == null) {

            return false;

        }

        if (root.key == key) {

            return true;

        }

        return key < root.key ? searchRec(root.l_value, key) : searchRec(root.r_value, key);

    }

     public static void main(String[] args) {

        BinarySearchTreeEg bsteg = new BinarySearchTreeEg();

 

        // add the elements to the binary Search Tree

        bsteg.insert(510);

        bsteg.insert(230);

        bsteg.insert(40);

        bsteg.insert(27);

        bsteg.insert(675);

        bsteg.insert(120);

        bsteg.insert(9);

         // display the In-order traversal

        System.out.println("Inorder traversal:");

        bsteg.inorder();

        //Search the key element

        Scanner s1 = new Scanner(System.in);

        System.out.println("\n"+"Enter the key value to search:");

        int a =s1.nextInt();

        if(bsteg.search(a))

          System.out.println("The key is available");

        else

          System.out.println("The key is not available");

        s1.close();       

    }

}

Output:

C:\raji\blog>javac BinarySearchTreeEg.java

C:\raji\blog>java BinarySearchTreeEg

Inorder traversal:

9 27 40 120 230 510 675

Enter the key value to search:

230

The key is available

C:\raji\blog>java BinarySearchTreeEg

Inorder traversal:

9 27 40 120 230 510 675

Enter the key value to search:

234

The key is not available

This is way of implementing Binary search Tree and its operations. Hope you learnt the Binary Search Tree. Keep coding.