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

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

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.

``````class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
stack<TreeNode*> s;
bool b = false;
TreeNode *t = root;
while (t || !s.empty()) {
while (t) {
s.push(t);
t = t->left;
}
t = s.top(); s.pop();
if (b) return t;
if (t == p) b = true;
t = t->right;
}
return NULL;
}
};
``````

``````class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if (!p) return NULL;
inorder(root, p);
return suc;
}
void inorder(TreeNode *root, TreeNode *p) {
if (!root) return;
inorder(root->left, p);
if (pre == p) suc = root;
pre = root;
inorder(root->right, p);
}
private:
TreeNode *pre = NULL, *suc = NULL;
};
``````

``````class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode *res = NULL;
while (root) {
if (root->val > p->val) {
res = root;
root = root->left;
} else root = root->right;
}
return res;
}
};
``````

``````class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if (!root) return NULL;
if (root->val <= p->val) {
return inorderSuccessor(root->right, p);
} else {
TreeNode *left = inorderSuccessor(root->left, p);
return left ? left : root;
}
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/285

Binary Search Tree Iterator

Binary Tree Inorder Traversal

Inorder Successor in BST II

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

https://leetcode.com/problems/inorder-successor-in-bst/discuss/72653/Share-my-Java-recursive-solution

https://leetcode.com/problems/inorder-successor-in-bst/discuss/72662/*Java*-5ms-short-code-with-explanations

https://leetcode.com/problems/inorder-successor-in-bst/discuss/72656/JavaPython-solution-O(h)-time-and-O(1)-space-iterative

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation