Inorder successor of node in binary search tree

Inorder successor of node in binary search tree

Inorder traversal of tree visits left subtree first, then root node and then right subtree. Given a binary search tree, find inorder successor of a node. 

Inorder successor of a node is visited after the node in inorder traversal of binary search tree. In other words, it would be the next larger node in binary search tree.

inorder successor in BST
For example. if we take below tree as an example and do inorder traversal of it, traversal will be: 4,6,8,10,12,14,15.

If inorder successor of a node is asked, return next element in traversal. What is inorder successor if node 20? It’s 22. What about 30? It’s 37.

From description, algorithm is almost clear. Traverse entire tree in inorder and store it in an array. Whenever successor of a node is asked. search that in array and return its next element. Also, keep in mind that inorder traversal of a binary search tree is in sorted order, so binary search algorithm can be used to search a node. Overall complexity of this algorithm is dominated by traversal itself which is O(n) and with extra space requirement of O(n).

What if we don’t want to pre-scan tree and store it? This is a valid scenario when tree is modified frequently in between queries for inorder successor. In that case, previously stored traversal will be waste and we need to do another one. That is hell lot of computing wastage, not to mentioned extra space being used. Can we do better? Let’s take a tree and see if we can figure out some pattern? Candidates for inorder successor of a node are as follows:

  1. If there is right subtree of node, output is left most child in the right subtree.
  2. If there is no right subtree, output is the node where last left turn was taken to reach given node.

First and second conditions are mutually exclusive that means, if first is true then second does not hold and vice-a-versa.
What if node given is right most node in tree? In that case both conditions will return NULL as there is no right subtree and there was no left turn taken to reach the node.
To summarize algorithm: Traverse to the node and keep track of node last left turn. Once at node, check if there is right subtree, if yes, find minimum in right subtree and return. If not, then return node last left turn was taken.

Let’s see some examples, inorder successor of 8 is 10, because last left was taken at 10 and there is no right sub tree.

BST-1 (1)

Here, inorder successor of 12 is 14, because last left was taken at 14 and there is no right subtree
inorder successor in BST

Here inorder successor of 4 is 6, last left was taken at node 6.

BST-2 (2)

What is inorder successor of 10. Since 10 has right subtree, find minimum element in right subtree. So inorder successor of 10 will be 12, of 14 is 15 and of 6 would be 8.

BST-2 (4)

Algorithm to find inorder successor

1. Start with root. Initialize successor as NULL.
2. If given node less than root, then search on left side and update successor. 
3. If node is greater than root, then search in right part, don't update successor.
4. When reached at node :
   4.1 If node has right subtree, return minimum node on right subtree. 
   4.2 Else return successor.
#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, int K){
 
    Node *successor = NULL;
    Node *current  = root;
    if(!root)
        return NULL;
 
    while(current->value != K){
        /* 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 1st left turn */
 
        if(current->value >K){
            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 right 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);
  root = addNode(root,37);
  root = addNode(root,45);
 
  Node *successor = inorderSuccessor(root, 40);
  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). However, there is no extra space required.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview to share, please contact us.

  • Tokala

    This code will not work if we have duplicates and one among those duplicates is root,and now search for the root data we get false results
    ex:
    insert in this order (5,-1,2,1,5,0,7)
    Now inorder print will be —> -1 0 1 2 5 5 7
    if i search for succesor of 5 i will not get 5,i get 7

    • http://algorithmsandme.in/ Jitendra Sangar

      Logically, answer 7 would be correct as it would be inorder successor of 5 at the root. But yes if we are talking about 5 which is left child of 5 at the root, answer will be wrong.
      But there is no way to find which 5 is being asked for? Other ways is function takes the pointer of the node and based on pointer comparison we check if this is asked node.

      Anyways thanks for pointing out the limitation of the algorithm. I will think of a solution and revert. Meanwhile if you have something, feel free to mail me.

  • student

    in function inorder_predecessor why u used sucessor node ?,i m bit confusing

    • http://algorithmsandme.in/ Jitendra Sangar

      Sorry for confusion. The variable name should be predecessor.

  • Pingback: Find two nodes with given sum in binary search tree (2Sum problem) – Algorithms and Me()

  • Pingback: Threaded binary search tree – Algorithms and Me()

  • Pingback: Inorder predecessor in binary search tree - Algorithms and Me()

  • Pingback: Delete node from binary search tree - Algorithms and Me()