# 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:**

![](https://assets.leetcode.com/uploads/2019/01/23/285_example_1.PNG)

```
**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:**

![](https://assets.leetcode.com/uploads/2019/01/23/285_example_2.PNG)

```
**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

```java
/**
 * 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

```java
/**
 * 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...

```java
// 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;
        }
    }
}
```