Searching In A Binary Search Tree In Java

May 24, 2021

Searching in a Binary Search Tree (BST)

A Binary Search Tree is a rooted binary tree whose internal nodes each a key greater than all the keys in the node’s left subtree and less than those in it’s right subtree. A Binary Search Tree is also called an ordered or sorted binary tree. In this article we will learn how to search a node in Binary search Tree.

Properties Of Binary Search Tree:-

All the node’s in the left subtree are less than the root node.
Similarly , All the node’s in right subtree are greater than the root node.
The left and right subtree each must also be a binary search tree.

These properties provides an ordering so that the operations like searching ,insertion, deletion, finding maximum key , minimum key can be done fast.

Example of a Binary Search Tree

Steps to find a node in Binary Search Tree

Suppose we want to search 17 in the above example

Step 1: Compare 17 with the root element which is 15.
Step 2: 17>15 , so Search for a node in right subtree.
Step 3: Compare 17 with 19 . i.e. 17<19 , so search for an element in left subtree.
Step 4: compare 17 with the left child of 19 . i.e. 17==17 , Hence, stop searching and return true.

Algorithm:

BinarySearchTree(tree):

Compare the node with the root of the tree.
If the node is matched then return the node itself.
Otherwise check if node value is less than the element present on root, If so then move to left subtree.
If node value is greater than the element present on root then move to the right subtree.
Repeat this procedure recursively until match found .
If element is not found then return null.

CODE FOR A BINARY SEARCH TREE IN JAVA

//Searching in Binary Tree

import java.util.*;
/*Representing a Node of a binary tree */
class Node{
    int value;
    Node left,right;
    Node(int value)
    {
        this.value=value; 
        left=null;
        right=null;
     }
}
class SearchNode
{
    Node root; //root of a binary search tree
    SearchNode()
    {
        root=null;
     }
    public Node searchNode(Node root,int value)
    {
        if(root==null)
            return null;
        if(root.value==value)   // return true if value is found in binary tree
            return root;
        else if(value <root.value)  
            return searchNode(root.left,value);  //traverse left subtree
        else 
            return searchNode(root.right,value);  //traverse right subtree
    }
     public static void main(String[] args) 
    {
        //Adding Nodes to the binary tree
        SearchNode tree=new SearchNode();
        tree.root=new Node(15);
        tree.root.left=new Node(9);
        tree.root.right=new Node(19);
        tree.root.left.left=new Node(5);
        tree.root.left.right=new Node(13);
        tree.root.right.left=new Node(17);
        tree.root.right.right=new Node(25);
        //calling search function if element is found then it will return true else return false
        Node node=tree.searchNode(tree.root,17);   
        if(node!=null)
            System.out.println("Element "+node.value+" is found in binary  tree");
         else 
            System.out.println("Element is not found in binary tree");
    }
}

Output:

Element 17 is found in binary tree

Time Complexity:

The run time complexity of a search operation using recursive way is O(h) where, h is a height of a Binary Search Tree .

In casae of a skewed Binary Search Tree the height is equal to the number of nodes in it ; so it become O(n) [worst -case].
In case of a Binary Search Tree built using some Tree Balancing Techniques like AVL, RED Black etc the height is equal to log(number of odes in it); so it becomes log(n). where, ‘n’ is the number ofnodes in a binary search tree.