# Find inorder predecessor for given key in a BST

Given a BST, find in-order predecessor of a given key in it. If the given key do not lie in the BST, then return the previous greater key (if any) present in the BST.

An in-order predecessor of a node in BST is the previous node in in-order traversal of it. For example, consider below tree

in-order predecessor of 8 do not exist.
in-order predecessor of 10 is 8
in-order predecessor of 12 is 10
in-order predecessor of 20 is 16

A node’s in-order predecessor is node with maximum value in its left sub tree i.e. its left subtree’s right-most child. If left subtree of the node doesn’t exists, then in-order predecessor is one of the ancestors of it. To find which ancestors is the predecessor, we can move up the tree towards root until we encounter a node which is right child of it’s parent. If any such node is found, the in-order predecessor is its parent else in-order predecessor do not exists for the node.

We can recursively check above conditions. The idea is to search for given node in the tree and update the predecessor to current node before visiting its right subtree. If the node is found in the BST, then we return maximum value node in its left subtree and if the left subtree of the node doesn’t exists, then in-order predecessor is one of the ancestors of it which is already been updated while searching for the given key.

Below is C++/Java implementation of the idea:

## Java

Output:

8 No Predecessor
10 Precessor is 8
12 Precessor is 10
15 Precessor is 12
16 Precessor is 15
20 Precessor is 16
25 Precessor is 20

The time complexity of above solution is O(n).

#### Iterative version –

The same algorithm can be easily implemented iteratively.

Below is C++/Java implementation of the idea:

## Java

Output:

8 No Predecessor
10 Precessor is 8
12 Precessor is 10
15 Precessor is 12
16 Precessor is 15
20 Precessor is 16
25 Precessor is 20

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon

Subscribe
Notify of
Guest
Thomas

Awesome!!

Guest
yndi

I believe your algorithm is too over complicated, you don’t need to handle the case when the current element is equal to the target one: