Inorder Successor in BST

Problem Description

Given the root of a binary search tree (BST) and a node p in it, find the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

A node q is the in-order successor of a node p if q is the node with the smallest key greater than p.val.

Naive Approach

One straightforward approach is to perform an in-order traversal of the BST and store the nodes in a list. Then, iterate through the list to find the node p and return the next node in the list. If p is the last node in the list, return null.

Algorithm

1. Perform an in-order traversal of the BST and store the nodes in a list.
2. Iterate through the list to find the node p.
3. If p is found and is not the last node in the list, return the next node.
4. Otherwise, return null.

Code (Python)

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

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the BST, because we need to traverse the entire tree to create the in-order list.
• Space Complexity: O(N), where N is the number of nodes in the BST, to store the in-order list.

Optimal Approach

Since it's a BST, we can improve efficiency by leveraging BST properties. We don't need to traverse the entire tree. The in-order successor must be the smallest node that is greater than the target node. We can traverse the tree, keeping track of the potential successor.

Algorithm

1. Initialize successor to null.
2. Start from the root and traverse down the tree.
3. If the current node's value is greater than p.val, it could be the successor. Update successor to the current node and go to the left subtree.
4. If the current node's value is less than or equal to p.val, the successor must be in the right subtree, so go to the right subtree.
5. Repeat steps 3 and 4 until the current node is null.
6. Return the successor.

Code (Python)

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

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

    return successor

Complexity Analysis

• Time Complexity: O(H), where H is the height of the BST. In the worst case (skewed tree), H can be N, where N is the number of nodes. In the best case (balanced tree), H is log(N).
• Space Complexity: O(1), because we only use a constant amount of extra space.

Edge Cases

• If p is the largest node in the BST, its in-order successor does not exist, and the algorithm should return null.
• If the tree is empty, the algorithm should return null.
• If p is not in the BST, the algorithm should return the smallest node that is greater than p.val, or null if no such node exists.