# 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.

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.

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

```#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){
}
else{
}
}

return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;

//Creating a binary tree