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

An inorder successor of a node in the BST is the next node in the inorder sequence. For example, consider the following 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 does not exist.

Practice this problem

A node’s inorder successor is the node with the least value in its right subtree, i.e., its right subtree’s leftmost child. If the right subtree of the node doesn’t exist, then the inorder successor is one of its ancestors. To find which ancestors are the successor, we can move up the tree towards the root until we encounter a node that is left child of its parent. If any such node is found, then inorder successor is its parent; otherwise, inorder successor does not exist for the node.

Recursive Version

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

Following is the C++, Java, and Python implementation of the idea:

C++


Download  Run Code

Java


Download  Run Code

Python


Download  Run Code

Output:
 
The successor of node 15 is 16
The successor of node 10 is 12
The successor of node 20 is 25
The successor of node 8 is 10
The successor of node 12 is 15
The successor of node 16 is 20
No Successor exists for node 25

The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.

Iterative Version

The same algorithm can be easily implemented iteratively. Following is the C++, Java, and Python implementation of the idea:

C++


Download  Run Code

Java


Download  Run Code

Python


Download  Run Code

Output:
 
The successor of node 15 is 16
The successor of node 10 is 12
The successor of node 20 is 25
The successor of node 8 is 10
The successor of node 12 is 15
The successor of node 16 is 20
No Successor exists for node 25

The time complexity of the above solution is O(n), where n is the size of the BST. The auxiliary space required by the program is O(1).