In this tutorial we will learn how to Search a key or element in Binary Search Tree (BST) with some examples. Search in BST is an important part in data structure.
What is Binary Search Tree(BST)?
A Binary Search Tree a Node based binary tree data structure which has the following properties.:
- Left subtree nodes always be less than the root node.
- Right subtree nodes always be greater than the root node.
- Left and right subtree is also BST without any duplicate node.
- By default, there is no duplicates.
How to Search in Binary Search Tree?
Follow the below process to find an element in BST. We can also use this BST process to find an element in an Array also. Explanation and code as below.
Code
Explanation:
1. Define the base condition “(root==null)”, in this case return false.
2. If the key is greater than the root node, then search in left subtree.
3. If the key is equal to the root node, then return true.
4. Else iterate using the Recursive function.
public class BinaryTreeBT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// creating binary search tree
public static Node createBST(Node root, int val) {
if (root == null) {
root = new Node(val);
return root;
}
if (root.data > val) {
root.left = createBST(root.left, val);
} else {
root.right = createBST(root.right, val);
}
return root;
}
// search a key in bst
public static boolean searchInBST(Node root, int key){
if(root == null){
return false;
}
if(root.data > key){
return searchInBST(root.left, key);
}else if(root.data == key){
return true;
}else{
return searchInBST(root.right, key);
}
}
public static void main(String[] args) {
int[] values = {12, 8, 10, 1, 3, 4, 6, 9, 15};
Node root = null;
// creating binary search tree
for(int i=0; i<values.length; i++){
root = createBST(root, values[i]);
}
// search in BST
if(searchInBST(root, 1)){
System.out.println("found");
}else{
System.out.println("Not found");
}
}
}
Answer: found
Time Complexity: O(h), Where h is the height of the BST.
Space Complexity: O(h), Where h is the of the BST. This is because the maximum amount of space needed to store the recursion stack would be h.
Learn about the BST. See in LeeteCode also from Here.
Thank you for reaching out this tutorial. You can comment in the comments section below for any doubt or question. You can also learn more tutorial from here. Data Structure is the way to getting high package, so you can follow the DSA Tutorials in this site. We are posting the solution of the DSA problems.
How to Post contents free in FlutterTPoint?
You can post your content or post free Here. Just create your account the start posting.