How to find the Lowest Common Ancestor (LCA) of two nodes in a Binary Tree

If you are given a binary tree and two nodes and you have to find the lowest common ancestor, you can use the following approach.

  1. If the binary tree itself is null, you don’t have any common ancestor. This is an error condition.
  2. If one of the two nodes is the root, then the root itself is the common ancestor.
  3. Otherwise, recursively start finding the ancestor on the left node and right node.
    • If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
    • If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
    • Otherwise, root is the Lowest common ancestor.

Java code to find the common ancestor of Binary Nodes

package com.icodejava.blog;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 13, 2014
 * Last Modified On - Mar 13, 2014
 */
public class LowestCommonAncestorBinaryTree {
	
	public static void main(String args[]) {
		/**
		 * Create a sample Binary Tree. A Binary tree does not have to maintain
		 * left <root < right relationship.
		 */
		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(4);
		root.left.left = new Node(6);
		root.left.right = new Node(5);

		root.right.left = new Node(9);
		root.right.right = new Node(11);
		root.right.right.left = new Node(7);
		root.right.right.right = new Node(3);

		System.out.println("Lowest Common Ancestor of Node 3 and 9 is: "
				+ findLowestCommonAncestor(root, root.right.right.right, root.right.left).value);
		
		System.out.println("Lowest Common Ancestor of Node 3 and null is: "
				+ findLowestCommonAncestor(root, root.right.right.right, null).value);
		
		System.out.println("Lowest Common Ancestor of Node 11 and null is: "
				+ findLowestCommonAncestor(root, root.right.right, null).value);

	}
	
	/**
	 * Recursive approach to find the Lowest Common Ancestor
	 * @param root
	 * @param a - first Node
	 * @param b - second Node
	 * @return Node that is lowest common ancestor of both a and b
	 */
	public static Node findLowestCommonAncestor(Node root, Node a, Node b) {

		Node left = null;
		Node right = null;

		if (root == null) {
			return null;
		}

		/**
		 * If Node a or Node b is also the root, then the root itself is lowest common ancestor
		 */
		if (root == a || root == b) {
			return root;
		}

		left = findLowestCommonAncestor(root.left, a, b);
		right = findLowestCommonAncestor(root.right, a, b);

		/**
		 * If Node a and Node b lie in the left, their Lowest Common Ancestor is in the left.
		 * If Node a and Node b lie in the right,their Lowest Common Ancestor is in the right.
		 * 
		 * Otherwise, root is the Lowest common ancestor.
		 */
		if (left != null && right != null) {
			return root;
		}

		return (left != null) ? left : right;
	}
}
/**
 * Binary Tree representation.
 */
class Node {
	Node left;
	Node right;
	int value;
	
	public Node(int value) {
		left = null;
		right = null;
		this.value = value;
	}
}

The output of running above program is:

Lowest Common Ancestor of Node 3 and 9 is: 4
Lowest Common Ancestor of Node 3 and null is: 3
Lowest Common Ancestor of Node 11 and null is: 11

Tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *