## Data Structure Interview Questions answers

### 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;
}