LeetCode 285: Inorder Successor in BST

Explanation

To find the inorder successor in a BST, we can follow these steps:

1. If the right child of the current node is not null, then the successor is the leftmost node in the right subtree.
2. If the right child of the current node is null, then we need to backtrack to find the successor. We keep track of the potential successor as we traverse the tree.
3. When we find the target node, if its right child is not null, then the successor is the leftmost node in the right subtree of the target node. Otherwise, the potential successor stored while traversing is the actual successor.

Time complexity: O(h), where h is the height of the BST. Space complexity: O(1) if not considering the recursion stack.

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while (root != null) {
            if (root.val > p.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return successor;
    }
}