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 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.
- 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
/*Representing a Node of a binary tree */
Node root; //root of a binary search tree
public Node searchNode(Node root,int value)
if(root.value==value) // return true if value is found in binary tree
else if(value <root.value)
return searchNode(root.left,value); //traverse left subtree
return searchNode(root.right,value); //traverse right subtree
public static void main(String args)
//Adding Nodes to the binary tree
SearchNode tree=new SearchNode();
//calling search function if element is found then it will return true else return false
System.out.println("Element "+node.value+" is found in binary tree");
System.out.println("Element is not found in binary tree");
Element 17 is found in binary tree
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.