Inorder Successor in BST

 Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        TreeNode cur = root;
        Stack<TreeNode> stk = new Stack<>();
        TreeNode prev = null;
        while (cur != null || !stk.isEmpty()) {
            if (cur != null) {
                stk.push(cur);
                cur = cur.left;
            } else {
                cur = stk.pop();
                if (prev == p) {
                    return cur;
                }
                prev = cur;
                cur = cur.right;
            }
        }
        return null;
    }
}

=============
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (p.right != null) {
            TreeNode res = p.right;
            while (res.left != null) {
                res = res.left;
            }
            return res;
        } else {
            TreeNode parent = root;
            TreeNode res = null;
            while (parent != p) {
                if (parent.val > p.val) {
                    res = parent;
                    parent = parent.left;
                } else {
                    parent = parent.right;
                }
            }
            return res;
        }
       
    }
}