Searching in Binary Search tree in C

Searching in Binary Search Tree in C

 

Here, in this page we will discuss searching in binary search tree in C. A binary search tree is a tree in which the data in left sub-tree is less than the root and the data in right sub-tree is greater than the root.Given a Binary Search tree and a key, check whether the key is present in the tree or not.

searching in binary tree

Algorithm :

 

  • If tree is empty return.
  • Check whether key is greater or smaller than root.
  • If greater, move to the right subtree. Otherwise move to the left subtree.
  • If Key is found return true.
searching in binary search tree in C

Code in C for Searching in Binary Search Tree

#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

bool check_element(node * root, int key) {
// If root is null, element is not found:Backtrack
if (root == NULL) {
return false;
}
// Check whether same or not
if (root -> data == key) {
return true;
}

if (root -> data > key) {
// Traverse the left subtree
return check_element(root -> left, key);
}
// Else Traverse the right subtree
else {
return check_element(root -> right, key);
}
}
int main() {
node *root = newNode(80);
root -> left = newNode(60);
root -> right = newNode(90);
root -> left -> left = newNode(40);
root -> left -> right = newNode(70);
root -> left -> left -> left = newNode(30);
root -> left -> left -> right = newNode(50);
if (check_element(root,50)) {
printf("Found\n");
}
else {
printf("Not Found\n");
}
return 0;
}
Output :

Found