# 236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: β€œThe lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

# Solution

Approach 1: Assume p and q always exist - Recursive. Count the number of nodes == p or q in subtree. If there's no matches, return None; if there's one match, return the match; if there's 2 matches, return the lca.

Approach 2: Iterative. Dfs to find both p and q while saving all parent relationships in a dict. When both are found, use the dict to backtrack the LCA (by finding all ancesters of one node, and backtrack the other's ancesters to match them).

Approach 3: Either p or q can be not existing - two vectors. Use each vector to store the path from the root to each target node. Then compare two vectors from the root and the last overlapped node is the answer.

Approach 4: Either p or q can be not existing - Recursive with inorder traversal.

Approach 5: Either p or q can be not existing - Recursive with postorder traversal.

# Code (Python)

Approach 1:

    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        if root == p or root == q:
            return root
        left_lca, right_lca = self.lowestCommonAncestor(root.left, p, q), self.lowestCommonAncestor(root.right, p, q)
        # return None if neither node is in the subtree
        if not left_lca and not right_lca:
            return None
        # return root if there's one node per subtree
        if left_lca and right_lca:
            return root
        # both nodes are in the same subtree
        if left_lca or right_lca:
            return left_lca if left_lca else right_lca

Approach 2:

    def lowestCommonAncestor(self, root, p, q):
        stack = [root]
        parents = {}
        num_found = 0
        while stack and num_found < 2:
            node = stack.pop()
            if node == p or node == q:
                num_found += 1
                cur_node = node
                if num_found == 1:
                    ancesters_of_first_found = set([root])
                    while cur_node != root:
                        ancesters_of_first_found.add(cur_node)
                        cur_node = parents[cur_node]
                if num_found == 2:
                    while cur_node != root:
                        if parents[cur_node] in ancesters_of_first_found:
                            return parents[cur_node]
                        cur_node = parents[cur_node]
                    return root
            if node.left:
                parents[node.left] = node
                stack.append(node.left)
            if node.right:
                parents[node.right] = node
                stack.append(node.right)

# Code (C++)

Approach 1:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// Assume p and q always exist.
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL || root == p || root == q)
            return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left == NULL)
            return right;
        else if (right == NULL)
            return left;
        else
            return root;
    }
};

Approach 3:

// Either p or q can be not existing - two vectors.
class Solution {
private:
    bool findTreeNode(TreeNode *root, TreeNode *target, vector<TreeNode*>& buf) {
        if (root == NULL)
            return false;
        buf.push_back(root);
        if (root == target ||
            findTreeNode(root->left, target, buf) ||
            findTreeNode(root->right, target, buf))
            return true;
        buf.pop_back();
        return false;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> bufP;
        vector<TreeNode*> bufQ;
        findTreeNode(root, p, bufP);
        findTreeNode(root, q, bufQ);
        int i = 0;
        for (; i < bufP.size() && i < bufQ.size(); ++i)
        {
            if (bufP[i] != bufQ[i])
                return bufP[i-1];
        }
        if (i >= bufP.size())
            return bufP[i-1];
        if (i >= bufQ.size())
            return bufQ[i-1];
        return NULL;
    }
};

Approach 4:

// Either p or q can be not existing - inorder.
class Solution {
private:
    TreeNode *res;
    int count;
    void doLowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q, bool checkRoot) {
        if (root == NULL)
            return;
        doLowestCommonAncestor(root->left, p, q, checkRoot);
        if (checkRoot)
        {
            if (count == 1 || (root == p || root == q))
                res = root;
        }
        if (root == p || root == q)
            count++;
        doLowestCommonAncestor(root->right, p, q, count > 0 ? false : true);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        res = NULL;
        count = 0;
        doLowestCommonAncestor(root, p, q, true);
        return res;
    }
};

Approach 5:

// Either p or q can be not existing - postorder.
class Solution {
private:
    TreeNode *res;
    bool doLowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL)
            return false;
        int left = doLowestCommonAncestor(root->left, p, q) ? 1 : 0;
        int right = doLowestCommonAncestor(root->right, p, q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid >= 2)
            res = root;
        return (left + right + mid >= 1);
/*
        bool left = doLowestCommonAncestor(root->left, p, q);
        bool right = doLowestCommonAncestor(root->right, p, q);
        if (left && right)
        {
            res = root;
            return true;
        }
        else if (!left && !right)
        {
            if (root == p || root == q)
                return true;
            else
                return false;
        }
        else if (root == p || root == q)
        {
            res = root;
            return true;
        }
        else
        {
            return true;
        }
*/
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        res = NULL;
        doLowestCommonAncestor(root, p, q);
        return res;
    }
};