# [leetcode] Inorder Successor in BST

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.

Note: If the given node has no in-order successor in the tree, return `null`.

o(h) time, o(1) space.

If root->val > p->val, root is a possible successor of p, move to root->left

otherwise do not change successor, move to root->right.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
TreeNode * succ = nullptr;
while(root != nullptr){
if(root->val > p->val){
succ = root;
root = root->left;
}else{
root = root->right;
}
}
return succ;
}
};```

This general solution can find the successor of a binary tree node.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
//extreme condition
if(p == NULL || root == NULL) return NULL;

//find next successor
if(p->right != NULL){
p = p->right;
while(p->left != NULL){
p = p->left;
}
return p;
}
else{
//p is root and has no right child
if(p == root) return NULL;

//find parent of p
TreeNode * parent = findParent(root, p);
//if p is left child of parent, return parent, else return NULL
while(parent->right == p && parent != root){
p = parent;
parent = findParent(root, p);
}
if(parent->left == p) return parent;
else return NULL;
}
}
TreeNode * findParent(TreeNode * root, TreeNode * p){
//base case
if(root == NULL) return NULL;
if(root->left == p || root->right == p){
return root;
}

TreeNode * q1 = findParent(root->left, p);
TreeNode * q2 = findParent(root->right, p);
return q1 == NULL? q2: q1;

}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.