In this Leetcode Lowest Common Ancestor of a Binary Tree problem solution we have 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).”

Leetcode Lowest Common Ancestor of a Binary Tree problem solution


Problem solution in Python.

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == None or root == p or root == q:
            return root

        l = self.lowestCommonAncestor(root.left, p, q)

        r = self.lowestCommonAncestor(root.right, p, q)

        if l and r:
            return root

        return l if l else r



Problem solution in Java.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }
        return left != null ? left : right;
    }
}


Problem solution in C++.

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

        TreeNode *leftLCA = lowestCommonAncestor(node->left,p,q);
        TreeNode *rightLCA = lowestCommonAncestor(node->right,p,q);

        if(leftLCA && rightLCA) return node;

        if(leftLCA) return leftLCA; else return rightLCA;
    }
};


Problem solution in C.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    return !left ? right : !right ? left : root;
}