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