Skip to main content

Lowest Common Ancestor of a Binary Tree

Problem​

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).”

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
    int cnt;
    TreeNode* LCA;

   public:
    int traverse(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return 0;
        int c = traverse(root->left, p, q) + traverse(root->right, p, q);
        c += (root->val == p->val) + (root->val == q->val);
        if (c == 2) {
            LCA = root;
            return 0;
        }
        return c;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        cnt = 0;
        traverse(root, p, q);
        return LCA;
    }
};