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 Binary Search Tree
Run
//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 class Main{
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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment