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.

inorder successor

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.

inorder successor

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

  1. Start with root, current = root, successor = NULL.
  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){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  int n = 0;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  Node *node = root;
  root = addNode(root,37);
  root = addNode(root,45);
  
  Node *successor = inorderSuccessor(root, node);
  printf("\n Inorder successor node is : %d ",successor ? successor->value: 0);
  
  return 0;
}

Complexity of algorithm to find inorder successor will be O(logN) in almost balanced binary tree. If tree is skewed, then we have worst case complexity of O(N).

Please share if there is something wrong or missing. If you want to contribute to website and share your knowledge with thousands of learners across the world, please reach out to us at communication@algorithmsandme.com