The basic idea is using a stack to store the path and finding the target node p. When find p,there are basically 3 cases:
1. If p has a right subtree, then just find the first left child of this subtree.
2. If p is the left child of its parent, then just return its parent
3. If p is the right child, the just track back the tree until find a node that meets requirement of 1. or 2.
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root==null  root.left==null && root.right==null  p==null) return null;
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode node=root;
while(node!=p){
stack.push(node);
if(p.val<=node.val && node.left!=null) node=node.left;
else if(p.val>node.val && node.right!=null) node=node.right;
else return null;
}
TreeNode visitedRight=null;
while(!stack.isEmpty() && stack.peek().right==node && node.right==visitedRight){
visitedRight=node;
node=stack.pop();
}
if(stack.isEmpty() && node.right==visitedRight) return null;
if(node.right==visitedRight) return stack.peek();
node=node.right;
while(node.left!=null)
node=node.left;
return node;
}
My Accepted Java O(lgN) Iterative Solution


Hi, @yucheyang2, thanks for the comment! I didn't quite get your point. would you mind post some part of your code so that we can understand it?

List<TreeNode> stack = new ArrayList<>(); TreeNode node = root; while (true) { if (target < node.val) { stack.add(node); node = node.left; } else if (target > node.val) { // stack.add(node); node = node.right; } else { if (node.right == null) { // Your case one and case two can combined to this. if (stack.isEmpty()) { return null; } else { return stack.remove(stack.size()  1); } } else { // Right Sub Tree Case node = node.right; while (node.left != null) { node = node.left; } return node; } } }