Given a binary search tree (BST) and a node p in it, find the in-order successor of that node in the BST.

The in-order successor of a node in a BST is the node with the smallest key greater than the key of the given node. If the given node has no in-order successor, return None.

You may assume that the given node has a parent pointer.

Function Signature:

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:
    """
    Find the in-order successor of a given node in a BST.

    Parameters:
    - root: The root of the binary search tree.
    - p: The node for which the in-order successor is to be found.

    Returns:
    - TreeNode: The in-order successor node or None if not found.
    """
    # Your code here

Example:

# 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

Note:

  • The given BST is a binary search tree, and the input node p is guaranteed to be a valid node in the BST.
  • The in-order successor is the node with the smallest key greater than the key of the given node p.
  • You may assume that the given node has a parent pointer.

Instructions:

  • Write the inorder_successor function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊