Write C code to search for a value in a binary search tree (BST)

There are two ways to solve this problem.

Algorithm:

1) Compere the root node if equal to data return

2) else if data < root value go to left sub tree

3) else if  data > root value go to right sub tree

Method 1 : Iterative approach

#include <stdio.h>

// here is the tree structure
typedef struct node
{
 int value;
 struct node *right;
 struct node *left;
}mynode;

// iterative approach
mynode *search(int value, mynode *root)
{
   while(root!=NULL && value!=root->value)
   {
      if(value < root->value)
         root = root->left;
      else
         root = root->right;
   }
   return(root);
}

Method 2: Recursive approach

Here is another way to do the same
// recursive approach

mynode *recursive_search(int item, mynode *root){

   if(root==NULL || item == root->value){
      return(root);
   }
   if(item < root->info)
   {
      return recursive_search(item, root->left);
   }
   else
   {
      return recursive_search(item, root->right);
   }
}

Complexity O(log N), Where N is the number of nodes in a tree.

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation