Tags: , , ,

# Inorder successor in binary search tree

What is an inorder successor in binary tree? Inorder successor is the node which traversed next to given node in inorder traversal of binary tree.  In binary search tree, it’s the next big value after the node. For example, inorder successor of node(6) in below tree will 10 and for node(12) it’s 14.

If node is the rightmost node or in BST, the greatest node, then there is no inorder successor for that node.

## Inorder successor : Thoughts

To find inorder successor, first thing to find is the node itself.  As we know in inorder traversal, root node is visited after left subtree.  A node can be successor for given node which is on left side of it.

Let’s come up with examples and see what algorithm works. First case, if the node is right most node of tree, there is no inorder successor, in that case return NULL. For example, successor for node 16 is NULL.

What if node has right subtree? In that case, minimum value in right subtree will be successor of given node.  We can find minimum value in tree by going deep down left subtree, till left subtree is NULL, and then return the last node. For example, successor node(5) is 6.

What are the other cases? Another case is that node does not have right subtree? Then parent of given node will be inorder successor. While moving down the tree on left side, keep track of parent node as it may be the solution. Successor of node(7) will be 10 as that’s where we moved to left subtree last time.  Note that we change successor candidate only  while moving down left subtree.

### Algorithm to find inorder successor

2. If `node.value` < `current.value`, then successor = current, current = current.left.
3. If `node.value` > `current.value`, current = current.right.
4. If `node.value` == `current.value` and node.right != null, successor = minimum(current.right).
5. Return successor

### Inorder successor : Implementation

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

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

typedef struct node Node;

//this function finds the minimum node in given tree rooted at node root
Node * findMinimum(Node *root){
if(!root)
return NULL;
// Minimum node is left most child. hence traverse down till left most node of tree.
while(root->left) root = root->left;
// return the left most node
return root;
}
/* This function implements the logic described in algorithm to find inorder successor
of a given node */
Node *inorderSuccessor(Node *root, Node *node){

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

while(current->value != node->value){
/* If node value is greater than the node which are looking for, then go to left sub tree
Also when we move left, update the successor pointer to keep track of lst left turn */

if(current->value > node->value){
successor = current;
current= current->left;
}
/* Else take right turn and no need to update successor pointer */
else
current = current->right;
}
/*Once we reached at the node for which inorder successor is to be found,
check if it has right sub tree, if yes then find the minimum in that right sub tree and return taht node
Else last left turn taken node is already stored in successor pointer and will be returned*/
if(current && current->right){
successor = findMinimum(current->right);
}

return successor;
}

Node * createNode(int value){
Node *newNode =  (Node *)malloc(sizeof(Node));

newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;

}

Node * addNode(Node *node, int value){
if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
int n = 0;
//Creating a binary tree
Node *node = root;