In Previous Post We learned about In-Order Successor.In this post ,We’ll learn what is In-Order Predecessor.

The predecessor of a node x in a search tree is the node with largest key that belongs to the tree and that is strictly less than x’s key.

In above binary search tree, in-order predecessor of 17 is 15 , predecessor of 6 is 4 and predecessor of 13 is 9.

Method to find out In-Order Predecessor is quite similar to Successor.

**Method 1**:

int maxValue(struct node* node) { struct node* n = node; while(n->right!=NULL) n=n->right; return n; } struct node* inOrderPredecessor(struct node* root,struct node* x) { if(x->left) return maxValue(x->left); else { struct node* y = x->parent; while(y !=NULL && x == y->left) { x = y; y = y->parent; } return y; } }

**Time Complexity** : O(h) where h is the height of tree.

**Method 2**:

struct node* inOrderPredecessor(struct node* root, struct node* x) { if( x->left != NULL ) return maxValue(x->left); struct node *predecessor = NULL; while (root != NULL) { if (x->data > root->data) { predecessor = root; root = root->right; } else if (x->data < root->data) root = root->left; else break; } return predecessor; }

**Time Complexity** : O(h)

I guess there is a bug in the Method 1:

You have not declared the variable “y”. I guess it should of Node type, meaning:

Node y;

Thanks,

Aditya

return type of max value is int or struct node* type

Alternate solution proposal. Can we do something like the following.

Do traditional In order traversal and instead of printing, put the value in a queue or an array. The next step of finding predecessor or successor is an easy one.

What if the number of elements are 1 millions? Are you going to follow this traditional in order traversal, complexity you know is then O(n). For less comlexity we use the upper method.