WAP to Find Inorder Successor of Given Node in Binary Search Tree With & Without Parent Pointer

Data Structure used: Binary Search Tree

Algorithm:
1) If right subtree of node is not NULL, then succ lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right sbtree of node is NULL, then succ is one of the ancestors. Do following.
Travel up using the parent pointer until you see a node which is left child of it’s parent. The parent of such a node is the succ.

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};

struct node * minValue(struct node* node);

struct node * inOrderSuccessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm
if( n->right != NULL )
return minValue(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;
}

/* Given a non-empty binary search tree, return the minimum data
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node * minValue(struct node* node) {
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return current;
}

/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;

return(node);
}

/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
struct node *temp;

/* 2. Otherwise, recur down the tree */
if (data <= node->data)
{
temp = insert(node->left, data);
node->left = temp;
temp->parent= node;
}
else
{
temp = insert(node->right, data);
node->right = temp;
temp->parent = node;
}

/* return the (unchanged) node pointer */
return node;
}
}

/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *temp, *succ, *min;

//creating the tree given in the above diagram
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->left->right->right;

succ = inOrderSuccessor(root, temp);
if(succ != NULL)
printf("\n Inorder Successor of %d is %d ", temp->data, succ->data);
getchar();
return 0;
}

Time Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/Bwwe6

2nd Method Without Using Parent Pointer

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;

};

/* Given a non-empty binary search tree, return the minimum data
value found in that tree. Note that the entire tree does not need
to be searched. */
struct node * minValue(struct node* node) {
struct node* current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return current;
}


struct node * inOrderSuccessor(struct node *root, struct node *n)
{
if( n->right != NULL )
return minValue(n->right);
struct node *succ=NULL;
while(root)
{
if(n->data < root->data)
{
succ=root;
root=root->left;
}
else if(n->data > root->data)
root=root->right;
else
break;
}
return succ;
}


/* Helper function that allocates a new node with the given data and
NULL left and right pointers. */
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);
}

/* Give a binary search tree and a number, inserts a new node with
the given number in the correct place in the tree. Returns the new
root pointer which the caller should then use (the standard trick to
avoid using reference parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

/* Driver program to test above functions*/
int main()
{
struct node* root = NULL, *temp, *succ, *min;

//creating the tree given in the above diagram
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 22);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 10);
root = insert(root, 14);
temp = root->left->right->right;

succ = inOrderSuccessor(root, temp);
if(succ != NULL)
printf("\n Inorder Successor of %d is %d ", temp->data, succ->data);
getchar();
return 0;
}

Time Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/4U9JI