Binary search tree is a tree structure defined by the following rules:
(1) for each parent node in the tree , the left child node value will be less than its value and the right child node value will be greater than its value.
(2) there can not be any duplicate node.
Clearly, creating a binary search tree, and searching a value in binary search tree works pretty much like bisection method; i.e. first we start with the root value, if it is lesser than the root value then we search with the lesser values only and if it greater than the root value, then we check with the greater values only. i.e.
the algorithm looks like something below in pseudocode:
search(value,node)
{
if (node==NULL)
{
print(value not found )
}
elseif(value>node->data)
{
search(value,node->right)
}
elseif(value < node->data)
{
search(value,node->left)
}
else(value==node->data)
{
print(value is found)
}
}
As you can understand on one minute on thinking, same algorithm can be used to create a binary search tree. Just, in case, when we hit NULL, we have to set that node to have the required value and to set its leaves as NULL.
Below, I have implemented the binary search tree creation and search function.
Try yourself first then, you can take a hint for the implemented code.
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *left;
struct node *right;
}stick;
stick *createnode(int data)
{
stick *newNode;
newNode=(stick *)calloc(1,sizeof(stick));
newNode->data=data;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
stick *binarysearchAndentry(int value,stick *node,int operation)
{
if(node==NULL)
{
if(operation==0)
{printf("%d is not in the tree",value);}
else
{
printf("%d is entered in appropiate position\n",value);
node=createnode(value);
return node;
}
}
else
{
if(node->left==NULL && node->data>value)
{
stick *lol;
lol=createnode(value);
node->left=lol;
printf("%d is entered in appropiate position\n",value);
}
else
{
if(node->right==NULL && node->data<value)
{
stick *lol;
lol=createnode(value);
node->right=lol;
printf("%d is entered in appropiate position\n",value);
}
else
{
if(value==node->data)
{
printf("%d is found in the tree",value);
}
else
{
if(node->data>value)
{
binarysearchAndentry(value,node->left,operation);
}
else
{
binarysearchAndentry(value,node->right,operation);
}
}
}
}
}
}
int main(void) {
stick *root;
root=binarysearchAndentry(20,NULL,1);
binarysearchAndentry(30,root,1);
binarysearchAndentry(10,root,1);
binarysearchAndentry(50,root,1);
binarysearchAndentry(25,root,1);
printf("%d\n",root->data);
printf("%d\n",root->left->data);
printf("%d\n",root->right->data);
printf("%d\n",root->right->right->data);
printf("%d\n",root->right->left->data);
return 0;
}
(1) for each parent node in the tree , the left child node value will be less than its value and the right child node value will be greater than its value.
(2) there can not be any duplicate node.
Clearly, creating a binary search tree, and searching a value in binary search tree works pretty much like bisection method; i.e. first we start with the root value, if it is lesser than the root value then we search with the lesser values only and if it greater than the root value, then we check with the greater values only. i.e.
the algorithm looks like something below in pseudocode:
search(value,node)
{
if (node==NULL)
{
print(value not found )
}
elseif(value>node->data)
{
search(value,node->right)
}
elseif(value < node->data)
{
search(value,node->left)
}
else(value==node->data)
{
print(value is found)
}
}
As you can understand on one minute on thinking, same algorithm can be used to create a binary search tree. Just, in case, when we hit NULL, we have to set that node to have the required value and to set its leaves as NULL.
Below, I have implemented the binary search tree creation and search function.
Try yourself first then, you can take a hint for the implemented code.
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *left;
struct node *right;
}stick;
stick *createnode(int data)
{
stick *newNode;
newNode=(stick *)calloc(1,sizeof(stick));
newNode->data=data;
newNode->left=NULL;
newNode->right=NULL;
return newNode;
}
stick *binarysearchAndentry(int value,stick *node,int operation)
{
if(node==NULL)
{
if(operation==0)
{printf("%d is not in the tree",value);}
else
{
printf("%d is entered in appropiate position\n",value);
node=createnode(value);
return node;
}
}
else
{
if(node->left==NULL && node->data>value)
{
stick *lol;
lol=createnode(value);
node->left=lol;
printf("%d is entered in appropiate position\n",value);
}
else
{
if(node->right==NULL && node->data<value)
{
stick *lol;
lol=createnode(value);
node->right=lol;
printf("%d is entered in appropiate position\n",value);
}
else
{
if(value==node->data)
{
printf("%d is found in the tree",value);
}
else
{
if(node->data>value)
{
binarysearchAndentry(value,node->left,operation);
}
else
{
binarysearchAndentry(value,node->right,operation);
}
}
}
}
}
}
int main(void) {
stick *root;
root=binarysearchAndentry(20,NULL,1);
binarysearchAndentry(30,root,1);
binarysearchAndentry(10,root,1);
binarysearchAndentry(50,root,1);
binarysearchAndentry(25,root,1);
printf("%d\n",root->data);
printf("%d\n",root->left->data);
printf("%d\n",root->right->data);
printf("%d\n",root->right->right->data);
printf("%d\n",root->right->left->data);
return 0;
}
Success #stdin #stdout 0s 9424KB
20 is entered in appropiate position 30 is entered in appropiate position 10 is entered in appropiate position 50 is entered in appropiate position 25 is entered in appropiate position 20 10 30 50 25
So this is the function to create and search and append function.
I have recently started to compile a solution bunch for hackerearth tree questions. Here is the github link for them below:
github link.
I have recently started to compile a solution bunch for hackerearth tree questions. Here is the github link for them below:
github link.
Comments
Post a Comment