Least Common Ancestor in a Binary Tree

In this article, we will implement the algorithm to find the least common ancestor(LCA) of two nodes in a given binary tree in Java. LCA of two nodes is the first common ancestor node of given nodes. For example, in the below binary tree the common ancestor of node 30 and node 25 is node 10.

Algorithm for LCA

We will basically use recursion to find the LCA. The algorithm recursively search for the nodes and if found the node is returned or else it returns null. Hence, for a node to be the common ancestor its left and right child must return a non-null node.

1. Search for the nodes
2. if (node found)
	return node;
 else
	return NULL;
3. When any node receives both the left and right child as non-null then it is the LCA
	else return what it receives.

Java Program to Find LCA

public class LCA {


    public static BinaryTreeNode findLCA(BinaryTreeNode root, BinaryTreeNode node1, BinaryTreeNode node2){
        if(root == null){
            return null;
        }
        if (root == node1 || root == node2) {
            return root;
        }
        BinaryTreeNode leftNode = findLCA(root.getLeftNode(), node1, node2);
        BinaryTreeNode rightNode = findLCA(root.getRightNode(), node1, node2);
        if (leftNode != null && rightNode != null){
            return root;
        }if (leftNode == null && rightNode == null){
            return null;
        }
        return leftNode == null? rightNode: leftNode; 
    }

}

Below is the binary tree node implementation.

Tree Runner

We have a main class that constructs the binary tree as per above diagram and invokes findLCA()

public static void main(String[] args){
        BinaryTreeNode root = new BinaryTreeNode(5);
        root.setLeftNode(new BinaryTreeNode(7));
        root.setRightNode(new BinaryTreeNode(10));
        root.getLeftNode().setLeftNode(new BinaryTreeNode(14));
        root.getLeftNode().setRightNode(new BinaryTreeNode(19));

        root.getRightNode().setLeftNode(new BinaryTreeNode(30));
        root.getRightNode().setRightNode(new BinaryTreeNode(15));

        root.getRightNode().getRightNode().setLeftNode(new BinaryTreeNode(25));
        BinaryTreeNode commonAncestor = LCA.findLCA(root, root.getRightNode().getLeftNode(), root.getRightNode().getRightNode().getLeftNode());
        System.out.println(commonAncestor.getData());
    }

Conclusion

In this article, we implemented the algorithm to find the Least Common Ancestor of given nodes.