Java Program to Search for an Element in a Binary Search Tree

This is a java program to search an element using Binary Search Tree. A regular tree traversal algorithm is implemented to search an element. We start from root, if value to be searched is less than root we traverse left, else we check if its greater we traverse right, else it is equal and return true.

Here is the source code of the Java Program to Search for an Element in a Binary Search Tree. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to search an element in binary search tree
import java.util.Random;
import java.util.Scanner;
 
/* Class BSTNode */
class BSTNode 
{
    BSTNode left, right;
    int data;
 
    /* Constructor */
    public BSTNode() 
    {
        left = null;
        right = null;
        data = 0;
    }
 
    /* Constructor */
    public BSTNode(int n) 
    {
        left = null;
        right = null;
        data = n;
    }
 
    /* Function to set left node */
    public void setLeft(BSTNode n) 
    {
        left = n;
    }
 
    /* Function to set right node */
    public void setRight(BSTNode n) 
    {
        right = n;
    }
 
    /* Function to get left node */
    public BSTNode getLeft() 
    {
        return left;
    }
 
    /* Function to get right node */
    public BSTNode getRight()
    {
        return right;
    }
 
    /* Function to set data to node */
    public void setData(int d) 
    {
 
        data = d;
    }
 
    /* Function to get data from node */
    public int getData() 
    {
        return data;
    }
}
 
/* Class BST */
class BST 
{
    private BSTNode root;
 
    /* Constructor */
    public BST() 
    {
        root = null;
    }
 
    /* Function to check if tree is empty */
    public boolean isEmpty() 
    {
        return root == null;
    }
 
    /* Functions to insert data */
    public void insert(int data) 
    {
        root = insert(root, data);
    }
 
    /* Function to insert data recursively */
    private BSTNode insert(BSTNode node, int data) 
    {
        if (node == null)
            node = new BSTNode(data);
        else 
        {
            if (data <= node.getData())
                node.left = insert(node.left, data);
            else
                node.right = insert(node.right, data);
        }
        return node;
    }
 
    /* Functions to delete data */
    public void delete(int k) 
    {
        if (isEmpty())
            System.out.println("Tree Empty");
        else if (search(k) == false)
            System.out.println("Sorry " + k + " is not present");
        else 
        {
            root = delete(root, k);
            System.out.println(k + " deleted from the tree");
        }
    }
 
    private BSTNode delete(BSTNode root, int k) 
    {
        BSTNode p, p2, n;
        if (root.getData() == k) 
        {
            BSTNode lt, rt;
            lt = root.getLeft();
            rt = root.getRight();
            if (lt == null && rt == null)
                return null;
            else if (lt == null) 
            {
                p = rt;
                return p;
            }
            else if (rt == null) 
            {
                p = lt;
                return p;
            }
            else 
            {
                p2 = rt;
                p = rt;
                while (p.getLeft() != null)
                    p = p.getLeft();
                p.setLeft(lt);
                return p2;
            }
        }
        if (k < root.getData()) 
        {
            n = delete(root.getLeft(), k);
            root.setLeft(n);
        }
        else 
        {
            n = delete(root.getRight(), k);
            root.setRight(n);
        }
        return root;
    }
 
    /* Functions to count number of nodes */
    public int countNodes() 
    {
        return countNodes(root);
    }
 
    /* Function to count number of nodes recursively */
    private int countNodes(BSTNode r) 
    {
        if (r == null)
            return 0;
        else 
        {
            int l = 1;
            l += countNodes(r.getLeft());
            l += countNodes(r.getRight());
            return l;
        }
    }
 
    /* Functions to search for an element */
    public boolean search(int val) 
    {
        return search(root, val);
    }
 
    /* Function to search for an element recursively */
    private boolean search(BSTNode r, int val) 
    {
        boolean found = false;
        while ((r != null) && !found) 
        {
            int rval = r.getData();
            if (val < rval)
                r = r.getLeft();
            else if (val > rval)
                r = r.getRight();
            else 
            {
                found = true;
                break;
            }
            found = search(r, val);
        }
        return found;
    }
 
    /* Function for inorder traversal */
    public void inorder() 
    {
        inorder(root);
    }
 
    private void inorder(BSTNode r) 
    {
        if (r != null) 
        {
            inorder(r.getLeft());
            System.out.print(r.getData() + " ");
            inorder(r.getRight());
        }
    }
 
    /* Function for preorder traversal */
    public void preorder() 
    {
        preorder(root);
    }
 
    private void preorder(BSTNode r) 
    {
        if (r != null) 
        {
            System.out.print(r.getData() + " ");
            preorder(r.getLeft());
            preorder(r.getRight());
        }
    }
 
    /* Function for postorder traversal */
    public void postorder() 
    {
        postorder(root);
    }
 
    private void postorder(BSTNode r) 
    {
        if (r != null) 
        {
            postorder(r.getLeft());
            postorder(r.getRight());
            System.out.print(r.getData() + " ");
        }
    }
}
 
public class Search_Element_BST 
{
    public static int N = 20;
 
    public static void main(String args[]) 
    {
        Random random = new Random();
        BST bst = new BST();
        for (int i = 0; i < N; i++)
            bst.insert(Math.abs(random.nextInt(100)));
 
        System.out.print("In order traversal of the tree :\n");
        bst.inorder();
 
        System.out.println("\nEnter the element to be searched: ");
        Scanner sc = new Scanner(System.in);
        System.out.println("Search result : " + bst.search(sc.nextInt()));
 
        sc.close();
    }
}

Output:

$ javac Search_Element_BST.java
$ java Search_Element_BST
 
In order traversal of the tree :
3 4 7 17 18 40 46 48 53 54 59 60 74 77 85 91 92 93 95 96 
Enter the element to be searched: 
51
Search result : false

Related posts:

Remove All Occurrences of a Specific Value from a List
Guide to the Synchronized Keyword in Java
Hướng dẫn Java Design Pattern – Prototype
Java Program to Construct a Random Graph by the Method of Random Edge Selection
Java Program to Implement CopyOnWriteArrayList API
Java Program to Implement Horner Algorithm
Lập trình đa luồng với CompletableFuture trong Java 8
Vấn đề Nhà sản xuất (Producer) – Người tiêu dùng (Consumer) và đồng bộ hóa các luồng trong Java
Java Program to Implement ScapeGoat Tree
Java Program to Implement Hash Trie
Java Program to Use Above Below Primitive to Test Whether Two Lines Intersect
Java Program to Perform Searching Using Self-Organizing Lists
Guide to DelayQueue
Java Program to Implement Warshall Algorithm
List Interface trong Java
Summing Numbers with Java Streams
Java Program to Implement Tarjan Algorithm
Derived Query Methods in Spring Data JPA Repositories
String Operations with Java Streams
Java Program to Create a Random Graph Using Random Edge Generation
How to Add a Single Element to a Stream
The SpringJUnitConfig and SpringJUnitWebConfig Annotations in Spring 5
Testing an OAuth Secured API with Spring MVC
SOAP Web service: Authentication trong JAX-WS
Java Program to Implement Sorted Circular Doubly Linked List
Java Program to Implement String Matching Using Vectors
Partition a List in Java
Comparing Dates in Java
Guide to @JsonFormat in Jackson
Spring Security Authentication Provider
Tiêu chuẩn coding trong Java (Coding Standards)
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph