#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