LeetCode 510: Inorder Successor in BST II

Explanation

In this problem, we are given a node in a binary search tree (BST) and we need to find the inorder successor of that node. The inorder successor of a node is the node with the smallest key greater than the node's key.

To solve this problem, we can follow these steps:

1. If the given node has a right child, then the inorder successor is the leftmost node in the right subtree.
2. If the given node does not have a right child, then we need to traverse up the tree until we find a node that is the left child of its parent. The parent node of such a node will be the inorder successor.

By following these steps, we can find the inorder successor for the given node efficiently.

Time complexity: O(h), where h is the height of the tree. Space complexity: O(1).

public Node inorderSuccessor(Node node) {
    if (node.right != null) {
        Node curr = node.right;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    } else {
        Node parent = node.parent;
        while (parent != null && node == parent.right) {
            node = parent;
            parent = parent.parent;
        }
        return parent;
    }
}