# Lowest Common Ancestot
###### tags: `coding interview` `binary search tree`

## Problem
https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/610/week-3-july-15th-july-21st/3819/

## Solution

### novice

class Solution {
    vector<TreeNode*> pStack;
    unordered_set<TreeNode*> qStack;
    
    void traverse(TreeNode *root, TreeNode *findNode, char type) {
        if (root == nullptr) return;
        
        
        if(type == 'p') {
                pStack.push_back(root);
        } else if (type == 'q') {
                qStack.insert(root);
        }
        
        if (root == findNode) return;
        
        if (findNode->val < root->val) {
            traverse(root->left, findNode, type);
        } else {
            traverse(root->right, findNode, type);
        }
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        traverse(root, p, 'p');
        traverse(root, q, 'q');
        
        TreeNode *ret = root;
        // find the common ancestor
        for (int i = 0; i < pStack.size(); i++) {
           if (qStack.count(pStack[i])) ret = pStack[i];
        }
        
        return ret;
    }
};

* Time Complexity: $O(logn)$
* Space Complexity: $O(logn)$

### space optimized (constant of space is smaller)

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return root;
        
        if ((root->val >= p->val && root->val <= q->val) || (root->val <= p->val && root->val >= q->val)) {
            return root;
        } else if (root->val < p->val && root->val < q->val) {
            TreeNode* r = lowestCommonAncestor(root->right, p, q);
            // root->right = nullptr;
            return r;
        } else {
            TreeNode* l =  lowestCommonAncestor(root->left, p, q);
            // root->left = nullptr;
            return l;
        }
    }
};

* Time Complexity: $O(logn)$
* Space Complexity: $O(logn)$

### more modulized code

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
            return NULL;
            
        if(root == p || root == q) return root;

        root->left = lowestCommonAncestor(root->left,p,q);
        root->right = lowestCommonAncestor(root->right,p,q);
        
        if(root->left!=NULL && root->right!=NULL)
            return root;
        else
            return root->left?root->left:root->right;
    }
};

* Time Complexity: $O(logn)$
* Space Complexity: $O(logn)$