17. Inorder Successor in BST

Given a binary search tree (See Definition) and a node in it, find the in-order successor of that node in the BST.

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

It's guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)

Example 1:

Input: {1,#,2}, node with value 1
Output: 2
Explanation:
  1
   \
    2

Example 2:

Input: {2,1,3}, node with value 1
Output: 2
Explanation: 
    2
   / \
  1   3

Solution: (Using Inorder Traversal)

class Solution {
public:
    /*
     * @param root: The root of the BST.
     * @param p: You need find the successor node of p.
     * @return: Successor of p.
     */
     vector<TreeNode *> v;

    void traverse(TreeNode *root){

        if(root == NULL){
            return;
        }
        traverse(root->left);
        v.push_back(root);
        traverse(root->right);
        
        return;
    }
    
    TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
        // write your code here
         
         if(root == NULL){
             return NULL;
         }

         traverse(root);

         int i;
         for(i=0;i<v.size();i++){
             if(v[i]->val == p->val){
                 break;
             }
         }
          i++;
          
         if(i == v.size()){
             return NULL;
         }


         return v[i];

    }
};

Solution: (Properties of BST)

Approach: If value is less than root then, root can be the successor and we check for Left Tree Else we got to right subtree

class Solution {
public:
    /*
     * @param root: The root of the BST.
     * @param p: You need find the successor node of p.
     * @return: Successor of p.
     */
    TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
        // write your code here

        TreeNode *t = root;
        if(root == NULL){
            return NULL;
        }

        TreeNode *succ = NULL;

        while(t!=NULL){
           
           if(p->val< t->val){
               succ = t;
               t = t->left;
           }
           else{
               t = t->right;
           }
        }

        return succ;
    }
};