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:

          15
         /  \
        /    \
       10     20
      / \     / \
     /   \   /   \
    8    12 16   25

– 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.

 
C++ implementation –
 

Download   Run Code

Output:

8 Successor is 10
10 Successor is 12
12 Successor is 15
15 Successor is 16
16 Successor is 20
20 Successor is 25
25 No Successor

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

Iterative version –

 
The same algorithm can be easily implemented iteratively.

 
C++ implementation –
 

Download   Run Code

Output:

8 Successor is 10
10 Successor is 12
12 Successor is 15
15 Successor is 16
16 Successor is 20
20 Successor is 25
25 No Successor

 
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 🙂
 

Get great deals at Amazon




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 btw in the beginning explanation there’s no key with the value 6.