Successor

Inorder Successor of an input node can also be defined as the node with the smallest key greater than the key of input node.

• Time: O(n)
• Space: O(1)

// Inorder Successor
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null) {
        return null;
    }
    if (root.val <= p.val) {
        return inorderSuccessor(root.right, p);
    } else {
        TreeNode node = inorderSuccessor(root.left, p);
        return node == null ? root : node;
    }
}

// Preorder Successor
public TreeNode preorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null) {
        return null;
    }
    if (root.val >= p.val) {
        return preorderSuccessor(root.left, p);
    } else {
        TreeNode node = preorderSuccessor(root.right, p);
        return node == null ? root : node;
    }
}