# 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;
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0285-inorder-successor-in-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.