











Searching In A Binary Search Tree In Java
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 searching in a 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 for Searching in 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.
Login/Signup to comment