Algo#1: Inorder Predecessor in Binary Tree

Inorder Predecessor value for any node X means value of node Y that comes just before 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 predecessor for any node by just looking at this traversal output. E.G. inorder predecessor of node '1' is node '5' because '5' appears before '1' in given traversal.

But in real life we encounter Inorder Predecessor to be search for randomly any node, and if we go by this method of doing inorder traversal first then giving predecessor, it would be inefficient because of its time complexity of O(n) in large trees. So we need some method which can return Inorder Predecessor 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 Predecessor for any node without doing traversal at all.

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

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

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

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

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

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

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

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

Following is implementation of above algorithm in c language.

/*
Algo#1: Inorder Predecessor in Binary Tree

Description: Find Inorder Predecessor value in given Binary Tree.
*/

#include 
#include 

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

Node *findRightMostNode(Node *root)
{
    while (root->right)
        root=root->right;
    return root;
}

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

Node *inorderPredecessor(Node *root, int key)
{
    return inorderPredecessorRec(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);
}

void deleteTree(struct node* node) 
{
    if (node == NULL) return;
 
    deleteTree(node->left);
    deleteTree(node->right);
   
    printf("\n Delete node: %d", node->data);
    free(node);
} 

int main()
{
  /*
            1
          /   \
        2      3
      /  \    /
    4     5  8
  */
  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(8);

  struct node * prede;
  prede = inorderPredecessor(root, 1);
  printf("Inorder Predecessor of %d is : %d\n",1,prede?prede->data:0);

  prede = inorderPredecessor(root, 2);
  printf("Inorder Predecessor of %d is : %d\n",2,prede?prede->data:0);

  deleteTree(root);
  getchar();
  return 0;
}

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