Inorder predecessor in binary search tree

Inorder predecessor

In last post we discussed inorder successor of a node in binary search tree. In today’s post, we will discuss another similar problem known as finding inorder predecessor of a node in BST.

What is inorder predecessor?

Going by symmetry with inorder successor, inorder predecessor of a node is node which comes just before it in inorder traversal of binary search tree. In other words, it’s the largest node prior to node.

inorder predecessor

For example in tree above, inorder predecessor of 25 is 20; for 37, it’s 30.

One way to find inorder predecessor is to traverse tree inorder and store nodes in an array. While predecessor is asked, just search for node in array and return node just prior to it. Since inorder traversal of a BST puts all nodes in sorted order, we can use binary search algorithm to find given node. However, drawback of this approach is use of extra memory and re-traversals if tree changes frequently.

Instead of traversing entire tree, can we use some kind of information we used while solving inorder successor problem. There are two conditions which will decide inorder predecessor of a node.

  1. If node has left subtree, then maximum element in that left subtree will be output.
  2. If node does not have left subtree, then node at which last right turn was taken is output. 

If node is left most node of tree, then there is no inorder predecessor as there will no right turn taken and there is no left subtree either, hence we should return null.

This is exact opposite of what we did for inorder successor, kind of symmetrical. Let’s take some examples and see if this algorithm works or not? In tree below, find predecessor of 8. Last right turn we took was at 6, and there is no left subtree of 8, hence the answer is 6.
inorder predecessor example
What is predecessor of 10 in inorder traversal of tree?  In this case there is a left subtree for node. Hence, find maximum in left subtree. Maximum node in BST is right most node of tree. Here, maximum of left subtree of 10 is 8, hence answer will be 8.
inorder predecessor implementation

Inorder predecessor implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node Node;
 
/* This function return the maximum node in tree 
rooted at node root */
Node *findMaximum(Node *root){
    if(!root)
        return NULL;
 
    while(root->right) root = root->right;

    return root;
}

/* 
This function implements the logic described in 
algorithm to find inorder predecessor of a given node
*/
Node *inorderPredecessor(Node *root, int K){
 
    Node *predecessor 	= NULL;
    Node *current  	= root;
 
    if(!root)
        return NULL;
 
    while(current && current->value != K){
        /* 
         Else take left turn and no need to 
         update predecessor pointer 
        */
        if(current->value >K){
            current= current->left;
        }
        /* 
           If node value is less than the node which 
           are looking for, then go to right sub tree
           Also when we move right, update the predecessor
           pointer to keep track of last right turn 
       */
        else{
            predecessor = current;
            current = current->right;
        }
    }
    /*
      Once we reached at the node for which inorder 
      predecessor is to be found,check if it has left 
      sub tree, if yes then find the maximum in that 
      right sub tree and return that node, Else last 
      right turn taken node is already stored in 
      predecessor pointer and will be returned
    */
    if(current && current->left){
        predecessor = findMaximum(current->left);
    }

    return predecessor;
}

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

  //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 *predecessor = inorderPredecessor(root, 40);
  printf("\n Inorder successor node is : %d ",
            predecessor ? predecessor->value: 0);
 
  return 0;
}

Complexity of finding inorder predecessor would be same as inorder successor i.e. O(logN).

Please leave a comment if you find something wrong or not clear enough, I will update. Remember sharing is caring. You can share this post anywhere you like with buttons given below.