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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Solution: Recursive

The idea is to traverse the tree starting from root.

1. If any of the given keys matches with root, then root if LCA (but we need to check if the other key is a child of the root).
2. If root doesn't match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA.
3. If both keys lie in left subtree, then left subtree has LCA, otherwise LCA lies in right subtree.

Time Complexity: Time complexity of the above solution is O(n) as the method does a simple tree traversal in bottom up fashion.

Note: This method assumes both keys are present in the tree. If one key is present and other is absent, then it returns the present key as LCA (Ideally should have returned NULL).

TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
    if (root == NULL) return NULL;

    if (root == A || root == B) return root;

    TreeNode *leftLCA = lowestCommonAncestor(root->left, A, B);
    TreeNode *rightLCA = lowestCommonAncestor(root->right, A, B);

    if (leftLCA && rightLCA) return root;

    return leftLCA != NULL ? leftLCA : rightLCA;
}

Solution: Storing the path

1. Find path from root to n1 and store it in a vector or array.
2. Find path from root to n2 and store it in another vector or array.
3. Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.

bool findPath(TreeNode *root, TreeNode *node, vector<TreeNode *> &paths) {
    if (!root) return false;

    paths.push_back(root);

    if (root == node) return true;

    if ((root->left && findPath(root->left, node, paths)) ||
        (root->right && findPath(root->right, node, paths))) {
        return true;
    } 

    paths.pop_back();
    return false;
}

TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
    if (root == NULL) return NULL;

    vector<TreeNode *> pathA, pathB;

    // Find paths from root to n1 and root to n1. If either n1 or n2
    // is not present, return NULL
    if (!findPath(root, A, pathA) || !findPath(root, B, pathB)) return NULL;

    // Compare the paths to get the first different value
    int i;
    for (i = 0; i < pathA.size() && i < pathB.size() ; i++)
        if (pathA[i] != pathB[i]) break;
    return pathA[i-1];;
}

Solution: Optimized

To handle cases when keys are not present in the tree.

TreeNode *findLCAUtil(TreeNode* root, TreeNode *A, TreeNode *B, bool &v1, bool &v2) {
    if (!root) return NULL;

    if (root == A) {
        v1 = true;
        return root;
    }

    if (root == B) {
        v2 = true;
        return root;
    }

    // Look for keys in left and right subtrees
    TreeNode *left_lca  = findLCAUtil(root->left, A, B, v1, v2);
    TreeNode *right_lca = findLCAUtil(root->right, A, B, v1, v2);

    // If both of the above calls return Non-NULL, then one key
    // is present in once subtree and other is present in other,
    // So this node is the LCA
    if (left_lca && right_lca)  return root;

    // Otherwise check if left subtree or right subtree is LCA
    return (left_lca != NULL)? left_lca: right_lca;
}

// Returns true if key k is present in tree rooted with root
bool find(TreeNode *root, TreeNode *node) {
    // Base Case
    if (root == NULL) return false;

    // If key is present at root, or in left subtree or right subtree,
    // return true;
    if (root == node || find(root->left, node) ||  find(root->right, node))
        return true;

    // Else return false
    return false;
}

TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
    // Initialize n1 and n2 as not visited
    bool v1 = false, v2 = false;

    // Find lca of n1 and n2 using the technique discussed above
    TreeNode *lca = findLCAUtil(root, A, B, v1, v2);

    // Return LCA only if both n1 and n2 are present in tree
    if (v1 && v2 || v1 && find(lca, B) || v2 && find(lca, A))
        return lca;

    // Else return NULL
    return NULL;
}