   # Implementation of Binary Search Tree in C

+1 vote
182 views

What is a Binary Seach Tree
A graph without any loop is called a tree which has exactly n-1 connectors/edges for n nodes and always have a unique path between any two nodes. If in this type of arrangement each node has two connection to child nodes and one to the parent node then it is called binary tree and if in this type of binary tree each left subnode is less then then parent node and rigt subnode is greater then parent then it is called binary seach tree.

See the following example - Necessary Operations
Delete Node
Search A Node
In Order Traversal
Post Order Traversal
Pre Order Traversal

Sample Code

``````struct node
{
int data;
struct node *lsubtree;
struct node *rsubtree;
};

struct node * create_node(int data)
{
struct node *new;

new = (struct node*)malloc(sizeof(struct node));
new->lsubtree = null;
new->rsubtree = null;
new->data = data;

return new;
}

{
{
}
{
}
{
}
}

struct node * inorder_successor(struct node* node)
{
struct node* current = node;

// loop down to find the leftmost leaf
while (current->lsubtree != NULL)
current = current->lsubtree;

return current;
}

struct node* delete_node(int data, struct node* root)
{
struct node *temp;

if (root == NULL) return root;

if (data < root->data)
root->lsubtree = delete_node(data, root->lsubtree);
else if (data > root->data)
root->rsubtree = delete_node(data, root->rsubtree);
else
{
// This is the node to be deleted

// node with only one child or no child
if (root->lsubtree == NULL)
{
temp = root->rsubtree;
free(root);
return temp;
}
else if (root->rsubtree == NULL)
{
temp = root->lsubtree;
free(root);
return temp;
}

// node with two children then get the inorder successor
temp = inorder_successor(root->rsubtree);

// Copy the inorder successor's content to this node
root->data = temp->data;

// Delete the inorder successor
root->rsubtree = delete_node(temp->data, root->rsubtree);
}

return root;
}

struct node *search(int data, struct node *head)
{
{
{
}
{
}
else
{
}
}
else return null;
}

void preorder_traversal (struct node * root)
{
if (root != NULL) {
printf("%c ", root->data);
preorder_traversal(root->lsubtree);
preorder_traversal(root->rsubtree);
}
}

void inorder_traversal (struct node * root)
{
if (root != NULL) {
inorder_traversal(root->lsubtree);
printf("%c ", root->data);
inorder_traversal(root->rsubtree);
}
}

void postorder_traversal (struct node * root)
{
if (root != NULL) {
postorder_traversal(root->lsubtree);
postorder_traversal(root->rsubtree);
printf("%c ", root->data);
}
}
`````` posted Sep 16, 2014
First time we have seen BST with delete operation (hope it is tested code)

## Related Articles ### What is a Cousin of a Node

Cousin of a node is a node or nodes which are at the same level but dont share the same parent. See the following image in which 12, 23, 54 and 76 are at the same level in which we can say 54 and 76 are the cousins of the node 12. Similarly 19 and 67 are the cousins of 9 and 14. ### How to find the cousins of the Node

Logic is very simple you need to find out the level of given node and its parent. Once you know the parent the job is easy i.e. traverse each node and check its level if level is same as given node level and its parent is not same as given node then its cousin or not.

### Code in C++

(picked from one of my old post)

``````using namespace std;

struct node{
struct node* left;
struct node* right;
int data;
};

using namespace std;

struct node{
struct node* left;
struct node* right;
int data;
};

// Traverse the tree in a way so that you can preserve the level and compare it with given level
void inorder(struct node* root,int present_level,int level,struct node* parent)
{
if(root!=NULL)
{
if(parent!=root)
inorder(root->left,present_level+1,level,parent);
if(level==present_level)
cout<<root->data<<" ";
if(parent!=root)
inorder(root->right,present_level+1,level,parent);
}
}

void make_tree(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=new node;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->data=data;
return;
}
else
{
if (((*root)->data)< data)
make_tree(&((*root)->right),data);
else
make_tree(&((*root)->left),data);
}

}

int height(struct node* node)
{
if (node==NULL)
return 0;
else
{

int lDepth = height(node->left);
int rDepth = height(node->right);

/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}

void print_level(node *root, int space, int level, int currlevel)
{
int i =0;
if ( currlevel == level )
{
for (i = 0; i < space; i++)
printf(" ");

if (root == NULL)
printf(" ");
else
printf("%d",root->data);

for (i = 0; i < space; i++)
printf(" ");

}
else
{
if(!root)
{
print_level(NULL, space, level, currlevel + 1);
print_level(NULL, space, level, currlevel + 1);
}
else
{
print_level(root->left, space, level, currlevel + 1);
print_level(root->right, space, level, currlevel + 1);
}
}
}

void print_tree(node *tree)
{
int hght = height(tree);
int width = (1 << ( hght + 1)) - 1;
int space = width / 2; int i;
for (i = 1; i <= hght; i++)
{
print_level(tree, space, i, 1);
printf("\n\n");
space = space / 2;
}
}

struct node* find_level_and_parent(struct node* root,int data,int* level)
{
struct node* parent=NULL;
struct node* child=root;

while(1)
{
if(child==NULL)
return NULL;
if(child->data==data)
{
return parent;
}
if(data>child->data)
{
parent=child;
child=child->right;
*level=*level+1;
}
else if(data<=child->data)
{
parent=child;
child=child->left;
*level=*level+1;
}
}
}

int main()
{
struct node* root=NULL;
make_tree(&root,50);
make_tree(&root,17);
make_tree(&root,72);
make_tree(&root,12);
make_tree(&root,23);
make_tree(&root,34);
make_tree(&root,54);
make_tree(&root,76);
make_tree(&root,9);
make_tree(&root,14);
make_tree(&root,19);
make_tree(&root,67);

print_tree(root);

int level=0;
struct node* temp=find_level_and_parent(root,12,&level);

if(temp!=NULL)
{
inorder(root,0,level,temp);
return 0;
}

return 1;
}
``````