Lowest Common Ancestor of a Binary Tree

Problem Statement

LeetCode-236: 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).”

Approach

The problem (a variation of Lowest Common Ancestor of a Binary Search Tree)can be solved using a recursive approach. The idea is to traverse the tree in a depth-first manner. Here are the steps:

1. If the root is null or the root is equal to p or q, return the root. This is because if root is null, it means no more potential candidates. If root == p || root == q, it means the function has found one of the nodes it is looking for.
2. Recursively find the LCA in the left subtree.
3. Recursively find the LCA in the right subtree.
4. If both the left and right subtrees return a non-null value, then the current root is the LCA. This scenario represents a case where both p and q are found in different branches (one in the left subtree and one in the right subtree). Thus, the current root has to be their lowest common ancestor.
5. If only one of the left or right subtrees returns a non-null value, then the LCA is in that subtree, so return the non-null node.

Implementation

Here is a Java implementation of the above approach:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // if root is null or root is one of the nodes
    if (root == null || root == p || root == q) {
        return root;
    }

    // recursively find the LCA in the left subtree
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // if both nodes are found in different subtrees
    if (left != null && right != null) {
        return root;
    }

    // both nodes are in the same subtree
    return left != null ? left : right;
}

Complexity Analysis

The overall time complexity of the algorithm is $O(N)$, where $N$ is the number of nodes in the binary tree. This is because we visit each node exactly once.

Follow-up

There is another approach to solve this problem using DFS.

private TreeNode ans = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    find(root, p, q);
    return ans;
}

// we need to evaluate 3 conditions
// 1. p/q at root
// 2. p/q in left
// 3. p/q in right
// for this we translate the boolean values to int values and compare the sum >= 2
// this means min 2 out of 3 boolean values are true
private boolean find(TreeNode root, TreeNode p, TreeNode q){
    // return false for null nodes
    if(null == root){
        return false;
    }

    // either p or q at curr node
    int curr = 0;
    if(root.val == p.val || root.val == q.val){
        curr = 1;
    }
    
    // p or q in left or right
    int left = find(root.left, p, q) ? 1 : 0;
    int right = find(root.right, p, q) ? 1 : 0;
    
    // check if we have found 2 nodes in either left or right or at curr
    // if yes, the curr is LCA
    if(left+right+curr >= 2){
        ans=root;
    }
    
    // found atleast 1?
    return left+right+curr > 0;
}

The time complexity of this approach is also $O(N)$, where $N$ is the number of nodes in the binary tree. This is because we visit each node exactly once.