Inorder Successor in BST II

Naive Solution

A naive solution to find the inorder successor of a node in a BST II involves traversing the entire tree in-order and then identifying the node that comes immediately after the given node.

1. Perform an in-order traversal of the BST and store the node values in a list.
2. Find the index of the given node in the list.
3. Return the node at the next index in the list if it exists; otherwise, return null.

Code:

def inorder_traversal(node, result):
    if node:
        inorder_traversal(node.left, result)
        result.append(node)
        inorder_traversal(node.right, result)


def naive_inorder_successor(node):
    result = []
    root = node
    while root.parent:  # Find the root of the tree
        root = root.parent

    inorder_traversal(root, result)
    
    for i in range(len(result)):
        if result[i] == node:
            if i + 1 < len(result):
                return result[i + 1]
            else:
                return None
    return None

Time Complexity: O(N), where N is the number of nodes in the tree because of in-order traversal.

Space Complexity: O(N), where N is the number of nodes in the tree to store the in-order traversal result.

Optimal Solution

The optimal solution leverages the properties of a BST and the presence of parent pointers to find the inorder successor more efficiently.

1. If the node has a right child, the inorder successor is the leftmost node in the right subtree.
2. If the node does not have a right child, we need to go up to the parent nodes until we find a node that is the left child of its parent. That parent is the inorder successor.
3. If we reach the root and still haven't found such a parent, it means the node is the rightmost node in the tree, and it has no inorder successor.

Code:

def inorder_successor(node):
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node
    
    while node.parent and node == node.parent.right:
        node = node.parent
        
    return node.parent

Time Complexity: O(H), where H is the height of the tree. In the worst-case scenario (skewed tree), H can be N, but in a balanced tree, it's log(N).

Space Complexity: O(1) because we use a constant amount of extra space.

Edge Cases

1. Node is None: If the input node is None, return None.
2. Node has right subtree: If the node has a right subtree, the successor is the leftmost node in that subtree.
3. Node is the rightmost node: If the node is the rightmost node in the tree, it doesn't have a successor; return None.
4. Empty Tree: This case is handled implicitly because you wouldn't be calling the function with a node from an empty tree.