Lowest Common Ancestor of a Binary Tree

Method 1 Find root to node path

https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

Find Path

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> fst, sec;
        search(root, fst, 4);

        // bug cout << it;  cout << (*it)->val; correct: it->val
        //for_each(fst.begin(), fst.end(), [](TreeNode* it){ std::cout << it->val << '\n';});
        for(auto it = fst.begin(); it != fst.end(); ++it) { cout << (*it)->val << endl; }

        return root;

    }

private:
    bool search(TreeNode* root, vector<TreeNode*>& res, int target) {
       if (root == nullptr) {
           //res.clear(); // bug
           return false;
        }

        res.push_back(root);
        if (root->val == target) {
            return true;
        }

        // may have problem
        // if find in left subtree, stop searching
        // if ( search(root->left, res, target) ) return true;
        // if ( search(root->right, res, target) ) return true;

        // !!!!!!!!!!!! Don't know this at the first time
        // If not present in subtree rooted with root, remove root from
       // path[] and return false
        if ( (root->left && findPath(root->left, path, k)) ||
         (root->right && findPath(root->right, path, k)) )
            return true;

        // buggy output if no this line
        res.pop_back();

        return false;
    }
};

       _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
[3,5,1,6,2,0,8,null,null,7,4]
search 4, Buggy output:
3
5
6
2
7
4

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> fst, sec;
        search(root, fst, p->val);
        search(root, sec, q->val);

        int i;
        for (i = 0; i < min(fst.size(), sec.size()); ++i) {
            if (fst[i]->val != sec[i]->val)
                break;
        }

        // bug return fst[i];
        return fst[i-1];      
    }

private:
    bool search(TreeNode* root, vector<TreeNode*>& res, int target) {
       if (root == nullptr) {
           return false;
        }

        res.push_back(root);
        if (root->val == target) {
            return true;
        }
        if ( search(root->left, res, target) ) return true;
        if ( search(root->right, res, target) ) return true;

        res.pop_back();
        return false;
    }
};

Method 2

https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-2-using-parent-pointer/

https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-tree-set-3-using-rmq/