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

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

**Note:**

1. If the given node has no in-order successor in the tree, return `null`.
2. It's guaranteed that the values of the tree are unique.

```cpp
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { // time: O(n); space: O(n)
    if (!root) return root;
    if (root->val <= p->val) {
        return inorderSuccessor(root->right, p);
    } else {
        TreeNode* left = inorderSuccessor(root->left, p);
        return !left ? root : left;
    }
}
```

```cpp
void helper(TreeNode* root, TreeNode* p, TreeNode*& prev, TreeNode*& succ) { // time: O(n); space: O(n)
    if (!root) return;
    helper(root->left, p, prev, succ);
    if (prev == p) succ = root;
    prev = root;
    helper(root->right, p, prev, succ);
}
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    if (!root || !p) return root;
    TreeNode* prev = nullptr, *succ = nullptr;
    helper(root, p, prev, succ);
    return succ;
}
```

```cpp
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { // time: O(n); space: O(n)
    stack<TreeNode*> st;
    TreeNode* cur = root;
    bool found = false;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top(); st.pop();
        if (found) return cur;
        if (cur == p) found = true;
        cur = cur->right;
    }
    return nullptr;
}
```

```cpp
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) { // time: O(n); space: O(1)
    if (!root) return root;
    TreeNode* cur = root, *successor = nullptr;
    while (cur) {
        if (cur->val <= p->val) {
            cur = cur->right;
        } else {
            successor = cur;
            cur = cur->left;
        }
    }
    return successor;
}
```


---

# 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://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/285.-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.