Search A Node In Binary Search Tree

Search A Node In Binary Search Tree

 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.

#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.

Search A Node In Binary Search Tree

 

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.

Insert A Node In Binary Search Tree

Binary Search Tree