Inorder Successor in BST

Naive Solution

A naive solution would involve performing an inorder traversal of the BST. During the traversal, we store the nodes we visit in an array. Then, we simply iterate through the array to find the node that comes after p. If p is the last node in the inorder traversal, then it has no inorder successor, so we return null.

Code

def inorder_successor_naive(root, p):
    inorder_list = []

    def inorder_traversal(node):
        if not node:
            return
        inorder_traversal(node.left)
        inorder_list.append(node)
        inorder_traversal(node.right)

    inorder_traversal(root)

    for i in range(len(inorder_list) - 1):
        if inorder_list[i] == p:
            return inorder_list[i+1]
    return None

Time Complexity

O(N), where N is the number of nodes in the BST, because we visit each node in the worst case.

Space Complexity

O(N), where N is the number of nodes in the BST, to store the inorder traversal in an array.

Optimal Solution

The optimal solution leverages the properties of a BST to find the inorder successor without needing to traverse the entire tree. Specifically, the inorder successor of a node p will be the smallest node in the BST that is greater than p. We can use this idea to traverse the tree.

1. Initialize successor = null.
2. Start from the root node.
3. While the current node is not null:
   • If p.val >= current_node.val: it means the inorder successor must be in the right subtree, so move to the right subtree.
   • Else: the current node is a potential successor. Update successor = current_node, and move to the left subtree (because a smaller value might still be the successor.)
4. Return the successor.

Code

def inorder_successor(root, p):
    successor = None
    curr = root

    while curr:
        if p.val >= curr.val:
            curr = curr.right
        else:
            successor = curr
            curr = curr.left

    return successor

Edge Cases

• If p is the largest value in the BST, it has no inorder successor, so the algorithm returns null.
• If the tree is empty, then the initial root is null, and the while loop will not execute, returning the initial successor, which is null.
• If p does not exist in the BST, the algorithm will still traverse the tree, but the logic will ensure that it returns the smallest node greater than a hypothetical node with value p.val.

Time Complexity

O(H), where H is the height of the BST. In the worst case (skewed tree), H can be equal to N (the number of nodes), resulting in O(N) time complexity. In the best case (balanced tree), H is log(N), so the time complexity is O(log N).

Space Complexity

O(1), because we are only using a constant amount of extra space, regardless of the size of the BST. We are simply updating pointers.