0285. Inorder Successor in BST

https://leetcode.com/problems/inorder-successor-in-bst

Description

Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

The successor of a node p is the node with the smallest key greater than p.val.

Example 1:

**Input:** root = [2,1,3], p = 1
**Output:** 2
**Explanation:** 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

Example 2:

**Input:** root = [5,3,6,2,4,null,null,1], p = 6
**Output:** null
**Explanation:** There is no in-order successor of the current node, so the answer is null.

Constraints:

• The number of nodes in the tree is in the range [1, 104].

• -105 <= Node.val <= 105

• All Nodes will have unique values.

ac

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode next;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        next = new TreeNode(Integer.MAX_VALUE);

        boolean canFind = findNext(root, (long) p.val + 1);


        if (!canFind && next.val == Integer.MAX_VALUE) return null;
        return next;
    }

    private boolean findNext(TreeNode root, long target) {
        // exit
        if (root == null) return false;

        // add smaller one to next
        if (root.val >= target && root.val < next.val) next = root;

        // handle
        if (root.val > target) {
            return findNext(root.left, target);
        } else if (root.val < target) {
            return findNext(root.right, target);
        } else {
            return true;
        }
    }
}

2/18/2018 version

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // edge cases
        if (root == null || p == null) return null;

        TreeNode res = p.right;
        while (res != null && res.left != null) res = res.left;
        if (res != null) return res;

        while (p != root) {
            if (p.val < root.val) {
                res = root;
                root = root.left;
            } else if (p.val > root.val) {
                root = root.right;
            }
        }

        return res;
    }
}
/*
when turn left, save value
*/

ac2: iterative

Genius solution...

// successor
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;

        if (root.val <= p.val) {
            return inorderSuccessor(root.right, p);
        } else {
            TreeNode left = inorderSuccessor(root.left, p);
            return left != null ? left : root;
        }
    }
}

// predecessor
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;

        if (root.val >= p.val) {
            return inorderSuccessor(root.left, p);
        } else {
            TreeNode right = inorderSuccessor(root.right, p);
            return right != null ? right : root;
        }
    }
}