Search A Node In Binary Search Tree (BST)

 In this post, you will learn how to search a node in a binary search tree using recursion.

To learn searching a node in BST first you need to learn about recursion, which is a function calling itself.

How To Search A Node In Binary Search Tree (BST)

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

struct node{  

    int key;
    struct node *left;
    struct node *right;

};

struct node *newnode(int val){

    struct node *new = malloc(sizeof(struct node));
    new->key   = val;
    new->left  = NULL;
    new->right = NULL;

    return new;

} 

int search(struct node *root, int key)
{
    if(root == NULL)
    return 0;
    if(root->key==key)
    return 1;
    if(root->key<key)
    return search(root->right, key);
    else
    return search(root->left, key);
}

struct node *insert(struct node *root, int val){
    if(root==NULL)
        return newnode(val);
    if(root->key<val)
        root->right = insert(root->right,val);
    else if(root->key>val)
        root->left = insert(root->left, val);
    return root;
}
    /* Let us create following BST

              50

           /     \

          30      70

         /  \    /  \

       20   40  60   80 */

int main(){
    struct node *root = NULL;
    root = insert(root,50);
    root = insert(root,30);
    root = insert(root,20);
    root = insert(root,40);
    root = insert(root,70);
    root = insert(root,60);
    root = insert(root,80);

    int key;
    scanf("%d",&key);
    printf("%d",search(root,key));
    return 0;
}

In Inorder traversal we traverse from left-root-right.

Explanation

  1. In this code, when we search a number it checks, whether the root data is equal to that number if yes then return 1 and if not then recursively call the function.
  2. First we will check if root is null, then there is no such element.
  3. Then we will check if the root’s data equal to the number or not.
  4. If not then we will check if it smaller or greater.
  5. If it is small then traverse to the left subtree.
  6. Again the function will call itself, and check if the root is null, then check if the root’s data equal. 
  7. Similarly this will continue till we get root’s data equal to the key or search element.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment