Lowest Common Ancestor

Medium

Python

def lca(root,p,q):
    if not root or root==p or root==q: return root
    left=lca(root.left,p,q)
    right=lca(root.right,p,q)
    return root if left and right else left or right

Java

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);
    return left!=null&&right!=null?root:left!=null?left:right;
}

Key Insight

'left or right' returns first truthy. Java needs ternary chain.

Python → Java Differences

'left and right' vs explicit null
'left or right' returns first non-None
Java ternary chain

Python

def lca(root,p,q):
    if not root or root==p or root==q: return root
    left=lca(root.left,p,q)
    right=lca(root.right,p,q)
    return root if left and right else left or right

Java

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);
    return left!=null&&right!=null?root:left!=null?left:right;
}

Algorithm Steps

1. Base case: null or target
2. Recurse both
3. Both found: current is LCA

← Previous All Trees Next →