10.md

Lowest Common Ancestor of a BST

Method 1

find the path of both the nodes then,the last common node in their be the answer

void called(TreeNode* root,TreeNode* f,vector<TreeNode*>&v )
    {
        if(root==NULL)  return;

        v.push_back(root);

        if(root->val == f->val )
            return;

        if(root->left!=NULL && root->val > f->val)
            called(root->left,f,v);

        else if(root->right!=NULL && root->val < f->val)
            called(root->right,f,v);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*>a1;
        called(root,p,a1);

        vector<TreeNode*>b1;
        called(root,q,b1);

        TreeNode* ans=NULL;
        for(int i=0;i<min(a1.size(),b1.size());i++)
            if(a1[i]->val==b1[i]->val)
                ans=a1[i];
            else
                break;
        return ans;
    }

METHOD 2

 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if(!root) return NULL;

        int cur=root->val;

        if(cur < p->val && cur < q->val)
            return lowestCommonAncestor(root->right,p,q);

        if(cur > p->val && cur > q->val )
            return lowestCommonAncestor(root->left,p,q);

        return root;
    }