Inorder Successor and Predecessor in a binary search tree

#include <stdio.h>
#include <stdlib.h>


typedef struct Node{

struct Node *left, *right;

int data;

}Node;


typedef Node * Tree;


Node * predecessor(Tree t, int el){

Node *prev = NULL;

while(t){

if(t->data < el){

prev = t;
t = t->right;

}else if(t->data == el){

if(t->left){

prev = t->left;

if(prev) {
while(prev->right)
prev = prev->right;
}
}

return prev;

}else {
t = t->left;

}
}

return NULL; //not in the tree

}


Node * successor(Tree t, int el){


Node *next = NULL;

while(t){

if(t->data > el){

next = t;
t = t->left;

}else if(t->data == el){

if(t->right){

next = t->right;

if(next){
while(next->left)
next = next->left;
}
}

return next;

}else {
t = t->right;
}
}
return NULL; //not in the tree
}


void insert(Tree t, int el)
{
if(el <= t->data)
{
if(t->left)
insert(t->left, el);
else
{
t->left = (Node *)calloc(sizeof(Node), 1);
t->left->data = el;
}
}
else
{
if(t->right)
insert(t->right, el);
else
{
t->right = (Node *)calloc(sizeof(Node), 1);
t->right->data = el;
}
}
}



int main(){

int n;

scanf("%d", &n);

int a[n];

int i;

for(i = 0; i < n; ++i){

scanf("%d", a + i);

}

Tree t = (Node *)calloc(sizeof(Node), 1);

t->data = a[0];

for(i = 1; i < n; ++i){

insert(t, a[i]);

}

int p;

scanf("%d", &p);

Node * v = predecessor(t, p);

if(v){

printf("Predecessor: %d\n", v->data);
}else{
printf("No Predecessor\n");
}


v = successor(t, p);

if(v){

printf("Successor: %d\n", v->data);
}else {
printf("No Successor\n");

}

return 0;


}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s