Find Inorder Successor for given key in a BST

Given a BST, find inorder successor of a given key in it. If the given key do not lie in the BST, then return the next greater key (if any) present in the BST.


 

An inorder successor of a node in BST is the next node in inorder traversal of it. For example, consider below bst:

 
Inorder successor and Inorder predecessor

 
– The inorder successor of 8 is 10
– The inorder successor of 12 is 15
– The inorder successor of 25 do not exist.

 

 
A node’s inorder successor is node with least value in its right subtree i.e. its right subtree’s left-most child. If right subtree of the node doesn’t exists, then inorder successor is one of the ancestors of it. To find which ancestors is the successor, we can move up the tree towards root until we encounter a node which is left child of it’s parent. If any such node is found, the inorder successor is its parent else inorder successor 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 successor to current node before visiting its left subtree. If the node is found in the BST, then we return least value node in its right subtree and if the right subtree of the node doesn’t exists, then inorder successor 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:

C++

Download   Run Code

Java

Download   Run Code

Output:

Successor of node 15 is 16
Successor of node 10 is 12
Successor of node 20 is 25
Successor of node 8 is 10
Successor of node 12 is 15
Successor of node 16 is 20
Successor doesn’t exists for 25

 
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:

C++

Download   Run Code

Java

Download   Run Code

Output:

Successor of node 15 is 16
Successor of node 10 is 12
Successor of node 20 is 25
Successor of node 8 is 10
Successor of node 12 is 15
Successor of node 16 is 20
Successor doesn’t exists for 25

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

 
Thanks for reading.

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 🙂
 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
kishore
Guest
kishore

It will be nice, if you can provide java source code.

Josep
Guest
Josep

Is the tree created properly? It seems creating the BST with a sorted array and the insert function in the code it should be a matter of taking the element.

In case you know the elements and have to create the tree, would be an option to just sort the array (nlogn) and take the closest bigger value in the array?

Thank you!