[TREE] Inorder successor and predecessor of a BST without parent pointer

Problem:
Find inorder successor/predecessor of given node in binary search tree.

In-order successor of a node is the node which will come after the given node in in-order traversal of binary search tree. In other words, it would be the next larger element in BST.

There are four cases:

1. If there is a right child of the given node. In this case the smallest element in the right sub tree would be the in-order successor.
2. If node does not have right sub tree and if last turn was right, then the node where we took the last left turn will be the in-order successor.
3. If node does not have right sub tree and if last turn was left turn, parent of the node is inorder successor.
4. If the node is the right most node, then there is no in-order successor.

It is clear from the analysis that we need to change the candidate only when we are moving towards left and not when moving right.

Algorithm

1. Start with root.
2. If the node is given has less than root, then search on left side and update successor.
3. If the node is greater than root, then search in right part, don't update successor.
4. If we find the node and if the node has right sub tree, then the minimum node on the right sub tree of node is the in-order successor.
5. Return successor

The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.

Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.

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 start from root and us search like technique. Do following.
   Travel down the tree, if a node’s data is greater than root’s data then go right side, otherwise go to left side.

struct node * inOrderSuccessor(struct node *root, struct node *n)
{
// step 1 of the above algorithm
if( n->right != NULL )
return minValue(n->right);

struct node *succ = NULL;

// Start from root and search for successor down the tree
while (root != NULL)
{
if (n->data data)
{
succ = root;
root = root->left;
}
else if (n->data > root->data)
root = root->right;
else
break;
}

return succ;
}

OR
Node * find_minimum(Node *root){
if(!root)
return NULL;

while(root->left){
root = root->left;

}
return root;
}

Node *inorder_success(Node *root, int K){

Node * successor = NULL;
Node *current = root;
if(!root)
return NULL;

while(current->value != K){
if(current->value >K){
successor = current;
current= current->left;
}
else
current = current->right;
}
if(current && current->right){
successor = find_minimum(current->right);
}

return successor;
}

Time Complexity: O(h) where h is height of tree.
Complexity of this algorithm will be O(logN) in almost balanced binary tree. If tree is skewed, then we have worst case complexity of O(N).

Inorder Predecessor:
Case 1: Node has left sub tree.
In this case the right most node in the left sub-tree would be the in-order predecessor.

Case 2: Node has no left sub-tree.
In this case in-order predecessor will be the node where we took the latest right turn.

Case 3 : Node is left most node of BST.
There is no in-order predecessor in this case and In this case there won't be any right turn.i.e. return NULL

Node * find_maximum(Node *root){
if(!root)
return NULL;

while(root->right){
root = root->right;

}
return root;
}

Node *inorder_preced(Node *root, int K){

Node * successor = NULL;
Node *current = root;
if(!root)
return NULL;

while(current && current->value != K){
if(current->value >K){
current= current->left;
}
else{
successor = current;
current = current->right;
}
}
if(current && current->left){
successor = find_maximum(current->left);
}

return successor;

}

Complexity analysis
Complexity of finding in-order predecessor would be same as successor i.e. O(logN).

PS
Method 1 (Uses Parent Pointer)
In this method, we assume that every node has parent pointer.

The Algorithm is divided into two cases on the basis of right subtree of the input node being empty or not.

Input: node, root // node is the node whose Inorder successor is needed.
output: succ // succ is Inorder successor of node.

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.

Implementation
Note that the function to find InOrder Successor is highlighted (with gray background) in below code.

#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;
}

---

Here is a non-recursive version of finding the successor. There are two cases: (i) the right child of node is not NULL. In this case, we can find the successor by finding the minimum element of the right substree. (ii) If the right child of node is NULL, the successor must either be NULL, or the lowest node on the path from root to node whose value is larger than node's value.

/*
* We assume that 'node' is in the tree
*/
Node * find_successor(Node * root, Node * node)
{
Node * y = root, * c = NULL;

if (node->right != NULL){
y = node->right;
while (y->left != NULL) y = y->left;
return y;
}

while ( y != node && y != NULL ){
if ( node->data data ){
c = y;
y = y->left;
}
else{
y = y->right;
}
}
return c;
}

Node * find_predecessor(Node * root, Node * node)
{
Node * y = root, *c = NULL;
if (node->left != NULL){
y = node->left;
while (y->right != NULL) y = y->right;
return y;
}

while ( y != node ){
if (node->data data){
y = y->left;
}
else {
c = y;
y = y->right;
}
}
return c;
}