/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<TreeNode> list = new ArrayList<>();
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        ldr(root,p);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).val==p.val){
                if (i+1==list.size()){
                    return null;
                }else {
                    return list.get(i+1);
                }
            }
        }
        return null;
    }
    public void ldr(TreeNode root,TreeNode p){
        if (root==null){
            return;
        }
        ldr(root.left,p);
        list.add(root);
        ldr(root.right,p);
    }
}

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode prev = null, curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev == p) {
                return curr;
            }
            prev = curr;
            curr = curr.right;
        }
        return null;
    }
}