Complexity Analysis

Time Complexity: O(N) where N is the number of nodes in the binary search tree. This complexity arises from the fact that we have to traverse all nodes in an inorder fashion to get to the inorder successor.

Space Complexity: O(1) as no additional data structure or memory allocation is done during the traversal and algorithm. Only a value comparison at each node.

Optimal Approach

Algorithm

Initialize a variable 'successor' as the maximum integer value.
Traverse the Binary Search Tree (BST) based on the key value.
If the current node value is smaller than the key, move to its right child.
If the current node value is greater than the key, update 'successor' to the minimum between the current 'successor' and the current node value, then move to the left child.
Continue this process until the traversal reaches a null node.

Code