To solve the “Inorder Successor in Binary Search Tree” problem, we can follow these steps:

  • If the given node p has a right child, then the in-order successor is the leftmost node in the right subtree.
  • If the given node p does not have a right child, then we need to traverse the tree upward from the given node until we find a node whose left child is an ancestor of p.

Here’s the implementation:

class TreeNode:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        if left != None: 
            self.left.parent = self
        self.right = right
        if right !=None:
            self.right.parent = self
        self.parent = parent

def inorder_successor(root: TreeNode, p: TreeNode) -> TreeNode:
    # Case 1: If the node has a right child, find the leftmost node in the right subtree
    if p.right:
        p = p.right
        while p.left:
            p = p.left
        return p

    # Case 2: If the node does not have a right child, traverse upward as long as p is the right child
    while p.parent and p.parent.right == p:
        p = p.parent

    # Exit the loop when p is the left child. Return the parent
    return p.parent

# Example BST:
#        5
#       / \
#      3   8
#     / \ / \
#    2  4 6  9

root = TreeNode(5)
root.left = TreeNode(3, TreeNode(2), TreeNode(4), root)
root.right = TreeNode(8, TreeNode(6), TreeNode(9), root)

result1 = inorder_successor(root, root.left)  
assert result1.val == 4
print(result1.val)
# Explanation: The in-order successor of node 3 is node 4

result2 = inorder_successor(root, root.right)  
assert result2.val == 9
print(result2.val)
# Explanation: The in-order successor of node 8 is node 9

result3 = inorder_successor(root, root.left.left)  
print(result3.val)
assert result3.val == 3
# Explanation: The in-order successor of node 2 is node 3

result4 = inorder_successor(root, root.left.right)  
print(result4.val)
assert result4.val == 5
# Explanation: The in-order successor of node 4 is node 5

result5 = inorder_successor(root, root.right.right)  
assert result5 is None
print(result5)
# Explanation: Node 9 has no in-order successor

Explanation:

  • If the given node p has a right child, we find the leftmost node in the right subtree. This is the smallest node greater than p in value.
  • If the given node p does not have a right child, we traverse upward from the node until we find a node whose left child is also an ancestor of p. The parent of this left-ancestor is the in-order successor.

Time Complexity:

The time complexity is O(H), where H is the height of the BST. In the worst case, we may need to traverse the height of the tree.

Space Complexity: The space complexity is O(1) as we are using a constant amount of additional space regardless of the input size.