Search an element in binary search tree





In this lesson we will learn how to Search an element in binary search tree. Given a root node and value of a binary search tree write a c program to find whether value is present or not. For example if the binary search tree is as

Given the tree:
        5
       / \
      2   6
     / \
    1   3

And the value to search: 3

Your program should return true or false. true means the value is present and false means value is not present in binary search tree.

Solution discussion:

Before diving into the solution let us know what is binary search tree. Binary search tree is special kind of binary tree where

  • The  value of every node in a node’s left sub-tree is less than the data value of that node.
  • The  value of every node in a node’s right sub-tree is greater than the data value of that node.

So with above property , what will you do for recursive solution?

  1. In your function , first check the base condition.
  2. Our base condition is if ( root->value == value ) return true.
  3. Else check if the value is less than the value present at root node , then search in left sub-tree.
  4. Otherwise search in right sub-tree.

Here is sample searching example in binary search tree

Recursive solution

#include<stdio.h>
#include<malloc.h>

#define true 1
#define false 0
#define NULL 0

typedef struct bst
{
    struct bst* left;
    struct bst* right;
    int value;
}bst;

bst* make_node(int value)
{
    bst* node = (bst*) malloc(sizeof(bst));
    node->left = NULL;
    node->right = NULL;
    node->value = value;
    return node;
}

int searchBst(bst* root, int value)
{
    // base condition
    if (root == NULL)  return false;
    if (root->value == value) return true;
    else if (value < root->value)
        return searchBst(root->left, value); // search left sub-tree
    else return searchBst(root->right, value); // search in right sub-tree
}

void freeMemory(bst* root)
{
    if (root == NULL) return;
    if (root->left)
        freeMemory(root->left);
    else
        freeMemory(root->right);
    free(root);
}

int main()
{
    // make bst tree
    bst* root = make_node(5); // root node
    root->left = make_node(2);
    root->right = make_node(6);

    root->left->left = make_node(1);
    root->left->right = make_node(3);

    printf("%d\n", searchBst(root, 2));
    // free memory
    freeMemory(root);
    root = NULL;
    return 0;
}

Search an element in binary search tree using iterative algorithm

#include<stdio.h>
#include<malloc.h>

#define true 1
#define false 0
#define NULL 0

typedef struct bst
{
    struct bst* left;
    struct bst* right;
    int value;
}bst;

bst* make_node(int value)
{
    bst* node = (bst*) malloc(sizeof(bst));
    node->left = NULL;
    node->right = NULL;
    node->value = value;
    return node;
}


void freeMemory(bst* root)
{
    if (root == NULL) return;
    if (root->left)
        freeMemory(root->left);
    else
        freeMemory(root->right);
    free(root);
}

int searchBst_itr(bst* root, int value) {
    while (root)
    {
        if (value == root->value)
            return true;
        if (value < root->value)
            root = root->left;
        else
            root = root->left;
    }
    return false;
}
int main()
{
    // make bst tree
    bst* root = make_node(5); // root node
    root->left = make_node(2);
    root->right = make_node(6);

    root->left->left = make_node(1);
    root->left->right = make_node(3);

    printf("%d\n", searchBst_itr(root, 2));
    // free memory
    freeMemory(root);
    root = NULL;
    return 0;
}

 



Related Contents to follow



No Comments Yet

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.