Lowest Common Ancestor in Binary Tree in DSA Java

Mental Model

Find the shared parent node closest to two given nodes in a tree. It is the deepest node that has both nodes as descendants.

Analogy: Imagine a family tree where you want to find the closest common grandparent of two cousins. You start from each cousin and move up until you find the first shared ancestor.

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

Dry Run Walkthrough

Input: Binary tree with nodes 3,5,1,6,2,0,8,7,4; find LCA of nodes 7 and 4

Goal: Find the lowest node that is an ancestor of both 7 and 4

Step 1: Start at root node 3, check left subtree for nodes 7 and 4

3 -> [curr->5] -> 1 -> ...

Why: We need to find nodes 7 and 4 in the tree starting from root

Step 2: At node 5, check left child 6 for nodes 7 and 4

3 -> 5 -> [curr->6] -> 2 -> ...

Why: 6 is not 7 or 4, check if subtree contains them

Step 3: 6 has no children with 7 or 4, return null up

3 -> 5 -> 6 -> null

Why: No target nodes found in 6's subtree

Step 4: At node 5, check right child 2 for nodes 7 and 4

3 -> 5 -> [curr->2] -> 7 -> 4

Why: 2's subtree may contain 7 and 4

Step 5: At node 2, check left child 7 matches target node 7

3 -> 5 -> 2 -> [curr->7]

Why: Found one target node

Step 6: At node 2, check right child 4 matches target node 4

3 -> 5 -> 2 -> 7 -> [curr->4]

Why: Found second target node

Step 7: Both targets found in 2's subtree, return node 2 as LCA

3 -> 5 -> [LCA->2] -> 7 -> 4

Why: Lowest node containing both targets is 2

Step 8: Return node 2 up to root, root returns node 2 as final LCA

[LCA->2]

Why: Final answer is node 2

Result:

2

Annotated Code

DSA Java

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class LowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q); // search left subtree
        TreeNode right = lowestCommonAncestor(root.right, p, q); // search right subtree

        if (left != null && right != null) return root; // p and q found in different subtrees
        return left != null ? left : right; // return non-null child or null
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        LowestCommonAncestor lcaFinder = new LowestCommonAncestor();
        TreeNode p = root.left.right.left; // node 7
        TreeNode q = root.left.right.right; // node 4
        TreeNode lca = lcaFinder.lowestCommonAncestor(root, p, q);
        System.out.println(lca.val);
    }
}

if (root == null) return null;

stop recursion if reached empty subtree

if (root == p || root == q) return root;

if current node is one target, return it

TreeNode left = lowestCommonAncestor(root.left, p, q);

search left subtree for targets

TreeNode right = lowestCommonAncestor(root.right, p, q);

search right subtree for targets

if (left != null && right != null) return root;

if targets found in both subtrees, current node is LCA

return left != null ? left : right;

return whichever subtree has a target or null

Output

2

Complexity Analysis

Time: O(n) because we visit each node once in the worst case

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to storing parent pointers and paths, this method uses no extra memory for parent maps and is simpler

Edge Cases

One or both nodes not present in tree

Returns null if neither node found; returns the found node if only one is present

DSA Java

if (root == p || root == q) return root;

Tree with only one node which is p and q

Returns that node as LCA immediately

DSA Java

if (root == p || root == q) return root;

Nodes are parent and child

Returns the parent node as LCA

DSA Java

if (left != null && right != null) return root;

When to Use This Pattern

When asked to find the closest shared ancestor of two nodes in a tree, use the Lowest Common Ancestor pattern because it efficiently finds the deepest common parent by recursive subtree checks.

Common Mistakes

Mistake: Returning root immediately without checking subtrees
Fix: Check left and right subtrees recursively before deciding if current node is LCA

Mistake: Not handling the case when one node is ancestor of the other
Fix: Return current node if it matches either target node

Summary

Finds the lowest node in a binary tree that is an ancestor of two given nodes.

Use when you need to find the closest shared parent of two nodes in a tree.

The key insight is that if one target is found in each subtree, the current node is their lowest common ancestor.

Practice

1. What is the Lowest Common Ancestor (LCA) of two nodes in a binary tree?

easy

A. The node that is a child of both nodes

B. The deepest node that is an ancestor of both nodes

C. The node with the smallest value between the two nodes

D. The root node of the binary tree

Solution

1. Step 1: Understand the definition of LCA

   The Lowest Common Ancestor is the deepest node in the tree that has both given nodes as descendants (a node can be a descendant of itself).

2. Step 2: Clarify the options

   The deepest node that is an ancestor of both nodes correctly describes the LCA. The root node is not always the LCA, and the smallest value or child relationships do not define LCA.

3. Final Answer:

   The deepest node that is an ancestor of both nodes -> Option B

4. Quick Check:

   LCA = deepest common ancestor [OK]

Hint: LCA is the deepest shared ancestor node [OK]

Common Mistakes:

• Confusing LCA with root node
• Thinking LCA is the smaller value node
• Assuming LCA is a child of given nodes

2. Which of the following is the correct Java method signature to find the LCA of two nodes in a binary tree?

easy

A. public void findLCA(TreeNode root, int n1, int n2)

B. public int findLCA(int root, TreeNode n1, TreeNode n2)

C. public TreeNode findLCA(int n1, int n2)

D. public TreeNode findLCA(TreeNode root, int n1, int n2)

Solution

1. Step 1: Analyze method parameters and return type

   The method should take the root node and two node values (or nodes) to find their LCA. It returns the TreeNode representing the LCA.

2. Step 2: Match with options

   public TreeNode findLCA(TreeNode root, int n1, int n2) matches this: it takes root and two integers, returns TreeNode. public int findLCA(int root, TreeNode n1, TreeNode n2) has wrong parameter types, C misses root, D returns void which is incorrect.

3. Final Answer:

   public TreeNode findLCA(TreeNode root, int n1, int n2) -> Option D

4. Quick Check:

   Correct signature includes root and returns TreeNode [OK]

Hint: LCA method needs root and two nodes, returns TreeNode [OK]

Common Mistakes:

• Omitting root parameter
• Wrong return type (void or int)
• Incorrect parameter order or types

3. Given the following binary tree and code snippet, what will be the output?

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

TreeNode lca = findLCA(root, 5, 1);
System.out.println(lca.val);

medium

A. 3

B. 5

C. 1

D. 2

Solution

1. Step 1: Identify nodes 5 and 1 in the tree

   Node 5 is left child of root 3, node 1 is right child of root 3.

2. Step 2: Find their lowest common ancestor

   The lowest common ancestor of 5 and 1 is the root node 3, as it is the deepest node that has both as descendants.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   LCA(5,1) = 3 [OK]

Hint: LCA of nodes on different sides is their root ancestor [OK]

Common Mistakes:

• Choosing one of the nodes instead of their ancestor
• Confusing child nodes as LCA
• Ignoring tree structure

4. The following Java method is intended to find the LCA of two nodes in a binary tree. What is the bug?

public TreeNode findLCA(TreeNode root, int n1, int n2) {
    if (root == null) return null;
    if (root.val == n1 || root.val == n2) return root;
    TreeNode left = findLCA(root.left, n1, n2);
    TreeNode right = findLCA(root.right, n1, n2);
    if (left != null && right != null) return root;
    if (left != null) return left;
    return right;
}

medium

A. It incorrectly returns root when both left and right are null

B. It returns null when both nodes are the same

C. It does not handle the case when one node is not present in the tree

D. It does not check for null root at the start

Solution

1. Step 1: Understand the method logic

   The method returns root if it matches either node, then recursively searches left and right subtrees. If both sides return non-null, root is LCA.

2. Step 2: Identify missing case

   The method assumes both nodes exist. If one node is missing, it may return the other node incorrectly as LCA without confirming presence of both.

3. Final Answer:

   It does not handle the case when one node is not present in the tree -> Option C

4. Quick Check:

   Missing node presence check causes incorrect LCA [OK]

Hint: Check both nodes exist before returning LCA [OK]

Common Mistakes:

• Ignoring missing node cases
• Assuming both nodes always exist
• Not validating subtree results properly

5. You have a binary tree where nodes can have duplicate values. How would you modify the standard LCA algorithm to correctly find the LCA of two nodes given their references (not values)?

hard

A. Use node references directly instead of comparing values during recursion

B. Use a hash map to store node values and find LCA by values

C. Ignore duplicates and return the first matching value node as LCA

D. Modify the tree to remove duplicates before finding LCA

Solution

1. Step 1: Understand the problem with duplicates

   When values are duplicated, comparing node values is unreliable to identify nodes uniquely.

2. Step 2: Use node references for comparison

   Instead of comparing values, compare the actual node references (memory addresses) to find exact nodes during recursion.

3. Step 3: Adjust algorithm accordingly

   Modify the LCA method to check if current node == target node references, not values.

4. Final Answer:

   Use node references directly instead of comparing values during recursion -> Option A

5. Quick Check:

   Use references, not values, for duplicates [OK]

Hint: Compare node references, not values, when duplicates exist [OK]

Common Mistakes:

• Comparing values instead of references
• Trying to remove duplicates unnecessarily
• Using value-based hash maps causing errors