Algo#2: Inorder Successor in Binary Tree

Inorder Successor value for any node X means value of node Y that comes just after node X while doing Inorder traversal. For given tree in figure, inorder traversal (Left Root Right) would be : 4 2 5 1 6 3. We can search inorder successor for any node by just looking at this traversal output. E.G. inorder successor of node '1' is node '6' because '6' appears after '1' in given traversal.

But in real life we encounter Inorder Successor to be search for any node randomly, and if we go by this method of doing inorder traversal first then giving successor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Inorder Successor randomly for any node without doing traversal explicitly in less time complexity.

Luckily inorder traversal follows some pattern which can help us in giving Inorder Successor for any node without doing traversal at all.

Following is simple algorithm for finding Inorder Successor of binary tree.

Step 1: Current root itself is NULL, then successor is also NULL.

Step 2: Current root contains value same as key for which we are looking successor.

        2.1: Current root has right child, then left most node of right child is successor.

        2.2: Current root doesn't has right child, then parent of current root is successor.

Step 3: Current root is not the target node for which we are looking successor.

        3.1: Search target node and its successor in left side of tree recursively, and return if found.

        3.2: Search target node and its successor in right side of tree recursively, and return.

Following is implementation of above algorithm in c language.

/*
Algo#2: Inorder Successor in Binary Tree

Description: Find Inorder Successor value in given Binary Tree.
*/
#include 
#include 

typedef struct node
{
    int data;
    struct node *left,*right;
} Node;

Node *findLeftMostNode(Node *root)
{
    while (root->left)
        root=root->left;
    return root;
}

Node *inorderSuccessorRec(Node *root, int key, Node *parent)
{
    //Case 1: Current root itself is NULL, then successor is also NULL.
    if (root==NULL)
        return 0;
    //Case 2: Current root contains value same as key for which we are looking successor.
    if (root->data == key)
    {
        //Case 2.1: Current root has right child, then left most node of right child is successor.
        if (root->right)
            return findLeftMostNode(root->right);
        //Case 2.2: Current root doesn't has right child, then parent of current root is successor.
        else
            return parent;
    }
    //Case 3: Current root is not the target node for which we are looking successor.
    else
    {
        //Case 3.1: Search target node and its successor in left side of tree recursively, and return if found.
        Node *left=inorderSuccessorRec(root->left,key,root);
        if (left)
            return left;
        //Case 3.2: Search target node and its successor in right side of tree recursively, and return.
        return inorderSuccessorRec(root->right,key,parent);
    }
}

Node *inorderSuccessor(Node *root, int key)
{
    return inorderSuccessorRec(root,key,NULL);
}

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

int main()
{

  /*
            1
          /   \
        2      3
      /  \    /
    4     5  6
  */
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);

  struct node * succ;

  succ = inorderSuccessor(root, 1);
  printf("Inorder Successor of %d is : %d\n",1,succ->data);

  succ = inorderSuccessor(root, 2);
  printf("Inorder Successor of %d is : %d\n",2,succ->data);

  getchar();
  return 0;
}

Please write comments if you find anything wrong or you want to add something more related to this topic.