Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

Search a Node in a Binary Search Tree (Searching in a BST)

Searching in a Binary Search Tree

Searching in Binary Search tree is the most basic program that you need to know, it has some set of rules that you need to follow, given below

Search a node in a Binary Search Tree

The basic set of Rules for Searching in BST

Consider the value that you need to search in a Binary search tree is called as data.

  • Start from the root node of BST
  • If the (root node value) == data, value found
  • Else, if (root node value) > data, then iterate to the left subtree
  • Else if (root node value) < data, then iterate to the right subtree
  • Keep on doing this until you find the value

Sample Example

Let’s assume that you want to find 12 in the example given on this page

  • Root node is 21
  • 21 > 12, so go to left subtree
  • 16 > 12, so again go to the left subtree
  • 10 < 12, so go to right subtree
  • 12 = = 12 this, found
Search a node in a Binary Search Tree Right Subtree

Program for Searching a node in a Binary Search Tree in C

// PrepInsta's program to do insertion in a Binary Search Tree (BST)
#include <stdio.h>
#include <stdlib.h>

// Basic struct of Tree
struct node
{
int val;
struct node *left, *right;
};

// Function to create a new Node
struct node* newNode(int item)
{
struct node* temp = (struct node *)malloc(sizeof(struct node));
temp->val = item;
temp->left = temp->right = NULL;
return temp;
}

// A sample C function to check if a given node exists in a binary search tree or not
int search(struct node* root, int value)
{
// while is used to traverse till the end of tree
while (root != NULL){

// checking condition and passing right subtree & recusing
if (value > root->val)
root = root->right;

// checking condition and passing left subtree & recusing
else if (value < root->val)
root = root->left;
else
return 1; // if the value is found return 1
}
return 0;
}

int main()
{
/*Root is created first*/
struct node* root = newNode(21);
root->left = newNode(16);
root->right = newNode(25);
root->left->left = newNode(10);
root->left->right = newNode(18);
root->right->left = newNode(22);
root->right->right = newNode(28);
root->left->left->left = newNode(8);
root->left->left->right = newNode(12);

int item = 10;

// Function to find item in the tree
int found = search(root,item);

if(found)
printf("%d value is found in the tree",item);
else
printf("%d value not found",item);

return 0;
}