Java Program to Find the Lowest Common Ancestor in a Binary Tree

This Java program finds the lowest common ancestor (LCA) of two nodes in a binary tree. The LCA is the deepest node that has both target nodes as descendants (where a node can be a descendant of itself).

Binary Tree Class with LCA Method

The BinaryTree class includes methods for adding nodes and finding the LCA. The approach used in the LCA method is recursive, which simplifies the problem into manageable subproblems.

public class BinaryTree {
    static class Node {
        int data;
        Node left, right;

        public Node(int item) {
            data = item;
            left = right = null;
        }
    }

    Node root;

    // Method to find LCA of two nodes n1 and n2
    public Node findLCA(int n1, int n2) {
        return findLCA(root, n1, n2);
    }

    // Recursive function to find LCA
    private Node findLCA(Node node, int n1, int n2) {
        if (node == null)
            return null;

        // If either n1 or n2 matches with root's key, report the presence by returning root
        if (node.data == n1 || node.data == n2)
            return node;

        // Look for keys in left and right subtrees
        Node left_lca = findLCA(node.left, n1, n2);
        Node right_lca = findLCA(node.right, n1, n2);

        // If both of the above calls return Non-NULL, then one key is present in one subtree and other is present in other,
        // So this node is the LCA
        if (left_lca != null && right_lca != null)
            return node;

        // Otherwise check if left subtree or right subtree is LCA
        return (left_lca != null) ? left_lca : right_lca;
    }

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

        Node lca = tree.findLCA(4, 5);
        System.out.println("LCA(4, 5): " + (lca != null ? lca.data : "None"));

        lca = tree.findLCA(4, 6);
        System.out.println("LCA(4, 6): " + (lca != null ? lca.data : "None"));
    }
}

Explanation of the findLCA Method

• The findLCA method first checks if the current node is null, which serves as the base case for recursion.
• If the current node matches one of the nodes we’re looking for, it returns that node, indicating that the current path could be part of the LCA path.
• The method recursively calls itself for the left and right children. If both children return non-null values, it means both nodes are found in different branches, so the current node is the LCA.
• If only one of the subtrees returns a non-null, that returned value will be the LCA.

Conclusion

This Java implementation effectively finds the LCA of two nodes in a binary tree. By using a recursive approach, the solution simplifies the complex problem of navigating through the tree structure to determine the LCA, making it efficient and easy to understand.