Find inorder successor and predecessor of a give

Interview Questions

Find inorder successor and predecessor of a given node in BST ......

Microsoft Interview Questions and Answers

44. Find inorder successor and predecessor of a given node in BST ......

Question:
Find inorder successor and predecessor of a given node in BST. Root node is given.
all cases should be include in single function.

maybe an answer2:

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

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

struct node *newNode(int data)
{
struct node *node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

void insert(struct node *&node, int data)
{
if(node == NULL)
{
node = newNode(data);
return;
}
else
{
if(data gt; node->data)
{
insert(node-gt;right, data);
}
else if(data <= node-gt;data)
{
insert(node->left, data);
}
}

}

void Inorder(struct node *root)
{
if(root != NULL)
{
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
}
}

node *minimum(node *p)
{
if(p == NULL)
return NULL;
while(p->left != NULL)
p = p->left;
return p;
}

node* maximum(node *p)
{
if(p == NULL)
return NULL;
while(p->right != NULL)
p = p->right;
return p;
}

node *Successor(node *root, node *p)
{
if(root == NULL || p == NULL)
return NULL;
if(p->right != NULL)
return minimum(p->right);
node *q = root;
node *parent = q;
if(q == p)
return NULL;
while(q != NULL)
{
parent = q;
if((q->data < p->data) && (q != p))
q = q->right;
else
break;
}
if(q == NULL || q != p)
return NULL;
return parent;
}

node *Predecessor(node *root, node *p)
{
if(NULL == p || NULL == root)
return NULL;
if(p->left != NULL)
{
return maximum(p->left);
}
node *q = root;
node *parent = q;
if(q == p)
return NULL;
while(q != NULL)
{
parent = q;
if(q->data >= p->data && (q != p))
q = q->left;
else
break;
}
if(q == NULL || q != p)
return NULL;
return parent;
}

node *findnode(node *root, int key)
{
if(NULL == root)
return NULL;
node *p = root;
while(p != NULL && key != p->data)
{
if(key <= p->data)
p = p->left;
else
p = p->right;
}

return p;
}

maybe an answer2:

/ InOrder Successor of a general Binary Tree. It can be even used for a BST . more optimisations // can be made for bst.
node * inOrderSuccessor(node *n)
{
// step 1 of the above algorithm
if( n->right != NULL )
return FindLeftMost(n->right);

// step 2 of the above algorithm
struct node *p = n->parent;
while(p != NULL && n == p->right)
{
n = p;
p = p->parent;
}
return p;
}

(Continued on next question...)