# Inorder Predecessor in Binary Search Tree

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 &amp;&amp; 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)

### 4 Thoughts on “Inorder Predecessor in Binary Search Tree”

1. Aditya on May 20, 2014 at 10:34 am said:

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,