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 ## 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  ## 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 Nodestruct 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 notint 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; } `