Solution Explanation: Inorder Successor in BST

This problem asks to find the in-order successor of a given node p in a Binary Search Tree (BST). The in-order successor is the node with the smallest key greater than p.val.

Approach: Iterative Search

The most efficient approach leverages the properties of a BST. In an in-order traversal of a BST, nodes are visited in ascending order of their values. Therefore, the successor of a node p can be found efficiently using an iterative approach.

1. Initialization: Start at the root of the BST. Initialize a variable ans to null. This variable will store the potential successor.

2. Iteration: Traverse the tree iteratively. For each node encountered:

   • If the node's value (root.val) is greater than p.val, this node is a potential successor. Update ans to this node. Then, explore the left subtree (because the successor must be the smallest value greater than p.val).
   • If the node's value is less than or equal to p.val, this node cannot be the successor. Explore the right subtree.

3. Termination: The loop terminates when root becomes null. At this point, ans holds the in-order successor if one exists; otherwise, ans remains null.

Time and Space Complexity

• Time Complexity: O(h), where h is the height of the BST. In the worst case (a skewed tree), h can be equal to n (the number of nodes). However, for balanced BSTs, h is O(log n).
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Implementation (Python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
        ans = None
        while root:
            if root.val > p.val:
                ans = root
                root = root.left
            else:
                root = root.right
        return ans
 

The code in other languages (Java, C++, Go, TypeScript, JavaScript) follows a very similar structure, adapting only the syntax specific to each language. The core logic remains consistent across all implementations.