285. 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.

How about Inorder predecessor ?

/**
 * 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) return null;
        TreeNode is;

        if(root == p){
            is = root.right;
            while(is != null && is.left != null) is = is.left;
            return is;
        }else if(root.val < p.val){
            return inorderSuccessor(root.right, p);
        }else{
            is = inorderSuccessor(root.left, p);
        }

        return is == null ? root : is;
    }
}

iterative

/**
 * 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) {
        TreeNode res = null;
        TreeNode target = null;
        Stack<TreeNode> stack = new Stack<>();

        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }

            TreeNode top = stack.pop();
            if(target != null){
                res = top;
                break;
            }
            if(p == top){
                target = top;
            }

            root = top.right;
        }

        return res;
    }
}