Java Coding Test Course, Finding Lowest Common Ancestor 1

Problem Definition

The problem is to find the Lowest Common Ancestor (LCA) of two nodes in a given binary tree. The LCA is the lowest node that is an ancestor of both nodes. This problem is an important example for understanding tree structures and recursive search methods.

For example, if we are given the following binary tree:

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

The LCA of nodes 5 and 1 is 3, and the LCA of nodes 5 and 4 is 5.

Problem Approach

There can be various approaches to solving this problem, but the most common method is to use Depth First Search (DFS). We will look at two approaches to solve the problem below.

1. Recursive DFS Approach

This method involves traversing the binary tree using recursion to check if each node is an ancestor of the two nodes. The basic idea is as follows:

• If the current node is null, return null.
• If the current node is one of the nodes we are looking for, return the current node.
• Recursively call on the left and right child nodes to get results.
• If both returned values from the left and right child nodes are not null, the current node is the LCA.
• In other cases, return the non-null child.

2. Searching Using a Parent Node Map

This method first creates a map to store the parents of each node and then proceeds as follows:

• Start with the first node and store its parent in the map.
• After storing the ancestor of the second node, verify each ancestor in the parent map.
• The first ancestor found while moving up from the first node to the second node is the LCA.

Java Code Implementation

Now let’s implement the two approaches described above in Java.

First Approach: Recursive DFS

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

public class Solution {
    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);
        
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}
            

Second Approach: Using Parent Node Map

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

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

public class Solution {
    private Map parentMap = new HashMap<>();
    
    public void buildParentMap(TreeNode root) {
        if (root.left != null) {
            parentMap.put(root.left, root);
            buildParentMap(root.left);
        }
        if (root.right != null) {
            parentMap.put(root.right, root);
            buildParentMap(root.right);
        }
    }
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        buildParentMap(root);
        
        HashSet ancestors = new HashSet<>();
        
        while (p != null) {
            ancestors.add(p);
            p = parentMap.get(p);
        }
        
        while (!ancestors.contains(q)) {
            q = parentMap.get(q);
        }
        return q;
    }
}
            

Test Cases

Let’s look at a few test cases to validate this implementation:

• Tree: Constructed as in the example above, find the LCA of nodes 5 and 1. The result should be 3.
• Tree: Also, find the LCA of nodes 5 and 4. The result should be 5.
• Tree: For nodes 6 and 7, the LCA should be 5.

Conclusion

In this article, we learned in detail how to find the Lowest Common Ancestor of a binary tree using Java. Using both recursive approaches and parent node maps allows us to effectively find the LCA. Understanding and implementing these algorithms provides a foundation for scoring well in programming interviews.

Building problem-solving skills is important, and practicing with various problems and gaining experience is necessary. Prepare for coding tests with sufficient practice!