Lowest Common Ancestor (LCA) in Java: Binary Trees and DAGs

Introduction to Lowest Common Ancestor (LCA)

The Lowest Common Ancestor (LCA) of two nodes p and q in a tree (or a Directed Acyclic Graph - DAG) is the lowest (i.e., deepest) node that has both p and q as descendants. A node can be a descendant of itself. The LCA problem is a classic in computer science, frequently appearing in technical interviews and having applications in areas like phylogenetic tree analysis and version control systems.

Understanding LCA is crucial for problems involving hierarchical data structures, where you need to find a common point of origin or divergence between two elements.

When Should You Think About LCA?

Consider using LCA when:

• You are given a tree (binary tree, N-ary tree) or a Directed Acyclic Graph (DAG).
• You need to find a common ancestor for two specific nodes.
• The problem involves relationships or paths between two nodes in a hierarchical structure.
• Problems related to file systems, organizational charts, or genetic trees.

Core Concepts of LCA

We will explore different approaches to finding the LCA, primarily focusing on binary trees, which can often be extended to N-ary trees or DAGs.

1. LCA in Binary Trees (Recursive Approach)

The most common approach for binary trees leverages recursion. The intuition is that if p and q are in different subtrees of a node root, then root must be their LCA. If both p and q are in the left subtree, then the LCA is in the left subtree. Similarly for the right subtree.

Algorithm:

1. Base Cases:
   • If root is null, return null.
   • If root is p or q, then root is the LCA (since a node can be a descendant of itself).
2. Recursive Calls: Recursively find LCA in the left subtree (leftLCA) and the right subtree (rightLCA).
3. Combine Results:
   • If both leftLCA and rightLCA are non-null, it means p is in one subtree and q is in the other. Thus, root is the LCA.
   • If only leftLCA is non-null, then both p and q (or one of them, and the other is an ancestor) are in the left subtree. So, leftLCA is the LCA.
   • If only rightLCA is non-null, then both p and q are in the right subtree. So, rightLCA is the LCA.
   • If both are null, neither p nor q were found in this subtree.

Example: LCA of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case 1: If root is null, or root is p or q, then root is the LCA
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recursively search in left and right subtrees
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // Case 1: Both p and q found in different subtrees
        if (leftLCA != null && rightLCA != null) {
            return root; // Current root is the LCA
        }
        // Case 2: Both p and q found in left subtree (or one is ancestor of other)
        else if (leftLCA != null) {
            return leftLCA;
        }
        // Case 3: Both p and q found in right subtree (or one is ancestor of other)
        else {
            return rightLCA;
        }
    }
}

Complexity:

• Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we might visit all nodes.
• Space Complexity: O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H can be N.

Dry Run: LCA in Binary Tree

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Tree structure:

      3
     / \
    5   1
   / \ / \
  6  2 0  8
    / \
   7   4

Result: 3

2. LCA in Binary Search Trees (BST) (Iterative Approach)

For Binary Search Trees, the property that all nodes in the left subtree are smaller and all nodes in the right subtree are larger than the root can be leveraged for a more efficient approach.

Algorithm:

1. Start from the root.
2. If both p and q are smaller than root.val, then LCA must be in the left subtree. Move root = root.left.
3. If both p and q are larger than root.val, then LCA must be in the right subtree. Move root = root.right.
4. If one node is smaller and the other is larger than root.val (or one of them is root itself), then root is the LCA.

class Solution {
    public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                return root; // Found split point or one of them is root
            }
        }
        return null; // Should not happen in a valid BST with p and q present
    }
}

Complexity:

• Time Complexity: O(H), where H is the height of the BST. In the worst case (skewed tree), H can be N.
• Space Complexity: O(1) for the iterative approach.

3. LCA in Directed Acyclic Graphs (DAGs)

Finding LCA in DAGs is more complex than in trees because a node can have multiple parents. One common approach involves finding all ancestors for both p and q and then finding the deepest common one.

Algorithm (Conceptual for DAGs):

1. Find Ancestors: For both p and q, find all their ancestors. This can be done using DFS or BFS starting from p and q and traversing edges in reverse (from child to parent).
2. Store Ancestors: Store the ancestors of p in a set and the ancestors of q in another set.
3. Find Common Ancestors: The intersection of these two sets gives the common ancestors.
4. Deepest Common Ancestor: From the common ancestors, the one with the largest depth (or furthest from the source node(s) in a topological sort) is the LCA.

This approach is generally O(V + E) for finding ancestors and then O(V) for finding the deepest common one. More optimized solutions for multiple LCA queries in DAGs exist, often involving heavy-light decomposition or binary lifting on a tree formed by ancestors.

Reusable Template for LCA in Binary Trees

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class LCASolution {
    /**
     * Finds the Lowest Common Ancestor (LCA) of two nodes in a binary tree.
     * @param root The root of the binary tree.
     * @param p The first node.
     * @param q The second node.
     * @return The LCA of p and q.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: If root is null, or root is p or q, then root is the LCA
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recursively search for p and q in the left and right subtrees
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // If both leftLCA and rightLCA are non-null, it means p and q are in different subtrees
        // of the current root. Thus, the current root is their LCA.
        if (leftLCA != null && rightLCA != null) {
            return root;
        }
        // If only leftLCA is non-null, it means both p and q (or one of them, and the other is an ancestor)
        // are in the left subtree. So, leftLCA is the LCA.
        else if (leftLCA != null) {
            return leftLCA;
        }
        // If only rightLCA is non-null, it means both p and q (or one of them, and the other is an ancestor)
        // are in the right subtree. So, rightLCA is the LCA.
        else {
            return rightLCA;
        }
    }

    /**
     * Finds the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST).
     * This iterative approach leverages the BST property.
     * @param root The root of the BST.
     * @param p The first node.
     * @param q The second node.
     * @return The LCA of p and q.
     */
    public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            // If both p and q are smaller than current root, LCA is in left subtree
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            }
            // If both p and q are larger than current root, LCA is in right subtree
            else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            }
            // Otherwise, current root is the LCA (either split point or one is ancestor of other)
            else {
                return root;
            }
        }
        return null; // Should not be reached if p and q are guaranteed to be in the BST
    }
}

How to Recognize LCA in Interviews

Look for these clues:

• Data Structure: Tree (binary, N-ary) or DAG.
• Goal: Find a common ancestor, especially the "lowest" or "deepest" one.
• Keywords: "Lowest Common Ancestor", "common parent", "shared ancestor", "path between two nodes" (LCA can be used to find the path).
• Applications: File system hierarchies, organizational charts, evolutionary trees.

Common Mistakes

Mistake 1: Not Handling Edge Cases

Forgetting null checks for the root or cases where p or q themselves are the root or an ancestor of the other node. The recursive solution naturally handles this by returning root if root == p or root == q.

Mistake 2: Confusing LCA with BST-specific properties

Applying the p.val < root.val && q.val < root.val logic to a general binary tree will lead to incorrect results, as it relies on the sorted property of BSTs.

Mistake 3: Incorrectly Handling Disconnected Nodes

If p or q are not present in the tree, or if the graph is disconnected (for DAGs), the LCA might not exist. The recursive binary tree solution will return null if neither p nor q are found in a subtree.

Mistake 4: Performance for Multiple LCA Queries

For a single LCA query, the recursive O(N) approach for binary trees is fine. However, if many LCA queries are needed on the same tree, pre-processing techniques like binary lifting or heavy-light decomposition can reduce query time to O(log N) or O(1) after O(N log N) pre-processing.

LCA vs. Other Tree/Graph Algorithms

• DFS/BFS: LCA solutions often use DFS implicitly (recursive approach) or explicitly (for ancestor finding in DAGs). DFS/BFS are general traversal techniques, while LCA is a specific problem.
• Tree Traversals (Pre-order, In-order, Post-order): These are ways to visit nodes. LCA uses the structure of these traversals to find the common ancestor.
• Graph Traversal (e.g., Dijkstra, BFS for shortest path): These are for pathfinding. LCA is about finding a common point in the hierarchy, not necessarily the shortest path between two nodes.

Practice Problems for This Pattern

1. Lowest Common Ancestor of a Binary Tree (LeetCode 236) - Standard recursive approach.
2. Lowest Common Ancestor of a Binary Search Tree (LeetCode 235) - Leverages BST properties.
3. Lowest Common Ancestor of a Binary Tree III (LeetCode 1676) - With parent pointers.
4. Lowest Common Ancestor of a DAG (More complex, often found in competitive programming or advanced graph theory problems).

Interview Script You Can Reuse

"This problem asks for the Lowest Common Ancestor (LCA) of two nodes in a binary tree. I'll use a recursive approach. The intuition is that if a node's left subtree contains one of the target nodes (p or q) and its right subtree contains the other, then the current node is their LCA. If both p and q are in the same subtree (either left or right), then the LCA must be in that subtree. The base cases are when the current node is null, or if it's p or q itself. The time complexity will be O(N) in the worst case, as we might visit all nodes, and space complexity will be O(H) for the recursion stack, where H is the height of the tree."

Final Takeaways

• LCA is the deepest node that has both p and q as descendants.
• For binary trees, a recursive DFS-like approach is common.
• For BSTs, an iterative approach leveraging the sorted property is more efficient.
• For DAGs, finding ancestors and then the deepest common one is a general strategy.
• Crucial for problems involving hierarchical relationships.
• Pay attention to edge cases and tree types (general binary tree vs. BST).

Mastering LCA is fundamental for understanding and solving problems related to tree and graph structures, especially those involving hierarchical relationships and common origins.

Read Next

• DSA in Java Series
• Bellman-Ford Algorithm in Java
• Kruskal’s Algorithm in Java
• Prim’s Algorithm in Java
• Matrix Traversal in Java
• Dijkstra’s Algorithm in Java
• Union Find (DSU) in Java
• Topological Sort in Java
• BFS (Breadth First Search) in Java
• DFS (Depth First Search) in Java
• Monotonic Queue Pattern in Java
• Monotonic Stack Pattern in Java
• Sorting Algorithms in Java
• Binary Search Pattern in Java
• In-place Reversal of a Linked List in Java
• Fast & Slow Pointers in Java
• Dutch National Flag Pattern in Java
• Kadane’s Algorithm in Java
• Prefix Sum Pattern in Java
• Sliding Window Pattern in Java
• Two Pointers Pattern in Java
• Big-O Notation in Java