Update: Added some optimization to the original code - skip the left subtree if p.val >= root.val during the traversal.

public class Solution {
TreeNode target = null;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null)
return null;
if (p.val < root.val) {
TreeNode n = inorderSuccessor(root.left, p);
if (n != null)
return n;
}
if (target == null) {
if (root.val == p.val)
target = root;
} else {
return root;
}
return inorderSuccessor(root.right, p);
} }