Search operation in Binary Tree
Search Operation
How to detect if a given key lies in the binary search tree or not.
- What is significance of learning about binary search trees since binary tree were equally
good.
- The major applications of using a binary search tree is to be able to search some key in the tree in logn time complexity in the best case where n is the number on nodes.
- Each time you compare a node with your key, you divide the search space to its half.
Searching in bellow illustrated example
- Key to search = 55.
- First compare our key with the root node itself, which is 50
- As the key(55) is more then root(50).
- And we know that right children have greater data value.
- So search in right subtree
- The first element we check our key with is 60.
- As key(55) is smaller then 60
- Search to the left of the current node.
- The left subtree of 60 contains only one element and since that is equal to our key
- Revert the positive result and the was found.
- And if the leaf node is not equal to the key, and since there are no subtrees further, the search will stop here with negative results, saying the key was not found.
Time complexity of the search operation in a binary search tree
-
The algorithm called binary search used for searching element in sorted array had the time
complexity of O(logn) where n was the length of the array.
- Beacuse we were always dividing our search space into half on the basis of whether our key was smaller or greater than the mid.
- Searching in a binary search tree is very much similar to binary search(for sorted array) algorithm.
- Searching in a binary search tree holds O(logn) time complexity in the best case where n
is the number of nodes making it incredibly easier to search an element in a binary search tree.
- and even operations like inserting get relatively easier.
- Let’s calculate exactly what happens. If you could see the above examples, the algorithm took
the number of comparisons equal to the height of the binary search tree, because at each
comparison we stepped down the depth by 1. So, the time complexity T ∝ h, that is, our time
complexity is proportional to the height of the tree. Therefore, the time complexity becomes
O(h).
Now, if you remember, the height of a tree ranges from logn to n, that is
(logn) ≤ h ≤ n
So, the best-case time complexity is O(logn) and the worst-case time complexity is O(n).
Psuedo code
- There will be a struct node pointer function search which will take the pointer to the root node and the key you want to serach in the tree.
- But first check if the root node is not NULL.
- If it is
- return NULL here itself
- Otherwise proceed further
- If it is
- Now check if the node you are at is the one you were looking for.. if it is, return that node. And that's it
- But if that is not the one, just see if that key is greater than or less than that node.
- If it is less
- Return recursively to the left subtree,
- otherwise return to the right subtree.
- And that's all.
Code
struct node * search(struct node* root, int key){
if(root==NULL){
return NULL;
}
if(key==root->data){
return root;
}
else if(key<root->data){
return search(root->left, key);
}
else{
return search(root->right, key);
}
}
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(int data){
struct node *n; // creating a node pointer
n = (struct node *) malloc(sizeof(struct node)); // Allocating memory in the heap
n->data = data; // Setting the data
n->left = NULL; // Setting the left and right children to NULL
n->right = NULL; // Setting the left and right children to NULL
return n; // Finally returning the created node
}
struct node * search(struct node* root, int key){
if(root==NULL){
return NULL;
}
if(key==root->data){
return root;
}
else if(key<root->data){
return search(root->left, key);
}
else{
return search(root->right, key);
}
}
int main(){
// Constructing the root node - Using Function (Recommended)
struct node *p = createNode(5);
struct node *p1 = createNode(3);
struct node *p2 = createNode(6);
struct node *p3 = createNode(1);
struct node *p4 = createNode(4);
// Finally The tree looks like this:
// 5
// / \
// 3 6
// / \
// 1 4
// Linking the root node with left and right children
p->left = p1;
p->right = p2;
p1->left = p3;
p1->right = p4;
struct node* n = search(p, 10);
if(n!=NULL){
printf("Found: %d", n->data);
}
else{
printf("Element not found");
}
return 0;
}
Iterative Search in a Binary Tree
- The search function we studied was a recursive function, calling the function recursively on the left or right subtree.
- Now we'll see the concept of searching iteratively in an binary search tree and its program code.
- In recursive approach
- You start with the root and compare your key with root node's data
- if it's smaller then the key
- you select the whole left subtree and start an interative approach
- We have tree intact the whole time.
- We just make a pointer run from the root to the place we expect our key to be.
struct node * searchIter(struct node* root, int key){
while(root!=NULL){
if(key == root->data){
return root;
}
else if(key<root->data){
root = root->left;
}
else{
root = root->right;
}
}
return NULL;
}
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(int data){
struct node *n; // creating a node pointer
n = (struct node *) malloc(sizeof(struct node)); // Allocating memory in the heap
n->data = data; // Setting the data
n->left = NULL; // Setting the left and right children to NULL
n->right = NULL; // Setting the left and right children to NULL
return n; // Finally returning the created node
}
struct node * searchIter(struct node* root, int key){
while(root!=NULL){
if(key == root->data){
return root;
}
else if(key<root->data){
root = root->left;
}
else{
root = root->right;
}
}
return NULL;
}
int main(){
// Constructing the root node - Using Function (Recommended)
struct node *p = createNode(5);
struct node *p1 = createNode(3);
struct node *p2 = createNode(6);
struct node *p3 = createNode(1);
struct node *p4 = createNode(4);
// Finally The tree looks like this:
// 5
// / \
// 3 6
// / \
// 1 4
// Linking the root node with left and right children
p->left = p1;
p->right = p2;
p1->left = p3;
p1->right = p4;
struct node* n = searchIter(p, 6);
if(n!=NULL){
printf("Found: %d", n->data);
}
else{
printf("Element not found");
}
return 0;
}