ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to find the Lowest Common Ancestor of two nodes in a Binary Search Tree/Binary Tree

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself). – Wikipedia

This article looks at creating a BST and then finding the LCA of two nodes in the tree. One way to do it is to find the path from the two nodes back to the root and find the first intersecting node for the two paths. This algorithm takes O(h) time where h is the height of the tree.

Below is a recursive algorithm in which starting from root traversing down we check if the two nodes are child of the current node being examined . If not the procedure is recursively carried on the child nodes until both nodes are children of the current node. Sometimes the two nodes being checked for can be a parent and child. This case is also tested to see if the current node itself is one of the node and if the other node is either the left or right child.

For example in the output : 99 and 120 are parent child so the LCA of parent child is a parent and thus 99

import java.io.*;
import java.util.*;

class Node
{
	public int item;
	public Node leftChild;
	public Node rightChild;
	public void displayNode()
	{
		System.out.print("[");
		System.out.print(item);
		System.out.print("]");
	}
}
class StackNode
{
	public Node item;
	public StackNode next;
	public StackNode(Node val)
	{
		item = val;
	}

}
class LinkedListStack
{
	private StackNode first;
	public LinkedListStack()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(Node key)//inserts at beginning of list
	{
		StackNode newLLNode = new StackNode(key);
		newLLNode.next = first;
		first = newLLNode;
	}
	public Node delete()//deletes at beginning of list
	{
		StackNode temp = first;
		first = first.next;
		return temp.item;
	}
}
class Stack
{
	private LinkedListStack listObj;
	public Stack()
	{
		listObj = new LinkedListStack();
	}
	public void push(Node num)
	{
		listObj.insert(num);
	}
	public Node pop()
	{
		return listObj.delete();
	}
	public boolean isEmpty()
	{
		return listObj.isEmpty();
	}
}

class Tree
{
	public Node root;
	public Tree()
	{ root = null; }
	public Node returnRoot()
	{
		return root;
	}
	public Node find(int val)
	{
		Node current = root;
		while(current.item != val)
		{
			if(val < current.item)
				current = current.leftChild;
			else
				current = current.rightChild;
			if(current == null)
				return null;
		}
		return current;
	}
	public void insert(int id)
	{
		Node newNode = new Node();
		newNode.item = id;
		if(root==null)
			root = newNode;
		else
		{
			Node current = root;
			Node parent;
			while(true)
			{
				parent = current;
				if(id < current.item)
				{
					current = current.leftChild;
					if(current == null)
					{
						parent.leftChild = newNode;
						return;
					}
				} 
				else
				{
					current = current.rightChild;
					if(current == null) 
					{
						parent.rightChild = newNode;
						return;
					}
				} 
			} 
		} 
	} 
	public int supportLCA(Node Root, Node a, Node b) 
	{
		int result = 0;
		if (Root == null) 
			return result;
		if (Root == a || Root == b) 
			result = result + 1;
		result = result + supportLCA(Root.leftChild, a, b);
		if(result == 2) 
			return result;
		return result + supportLCA(Root.rightChild, a, b);
	}
		
	public Node leastCommonAncestor(Node Root, Node a, Node b) 
	{
		if (b == a && (Root.leftChild == b || Root.rightChild == b)) 
			return Root;
		int nodesFromLeft = supportLCA(Root.leftChild, a, b); 
		if (nodesFromLeft == 2) 
		{
			if(Root.leftChild == a || Root.leftChild == b) 
				return Root.leftChild;
		
			else return leastCommonAncestor(Root.leftChild, a, b);
		} 
		else if (nodesFromLeft == 1) 
		{
		
			if (Root == a) 
				return a;
			else if (Root == b) 
				return b;
		}
		int nodesFromRight = supportLCA(Root.rightChild, a, b); 
		if(nodesFromRight == 2) 
		{
			if(Root.rightChild == a || Root.rightChild == b) 
				return Root.rightChild;
			else return leastCommonAncestor(Root.rightChild, a, b);
		} 
		else if (nodesFromRight == 1) 
		{
			if (Root == a) 
				return a;
			else if (Root == b) 
				return b;
		}
		if (nodesFromLeft == 1 && nodesFromRight == 1) 
			return Root;
	
		else return null;
	}

	public void displayTree()
	{
		Stack globalStack = new Stack();
		globalStack.push(root);	
		int emptyLeaf = 32;
		boolean isRowEmpty = false;
		System.out.println("****......................................................****");
		while(isRowEmpty==false)
		{

			Stack localStack = new Stack();
			isRowEmpty = true;
			for(int j=0; j<emptyLeaf; j++)
				System.out.print(' ');
			while(globalStack.isEmpty()==false)
			{
				Node temp = globalStack.pop();
				if(temp != null)
				{
					System.out.print(temp.item);
					localStack.push(temp.leftChild);
					localStack.push(temp.rightChild);
					if(temp.leftChild != null ||temp.rightChild != null)
						isRowEmpty = false;
				}
				else
				{
					System.out.print("--");
					localStack.push(null);
					localStack.push(null);
				}
				for(int j=0; j<emptyLeaf*2-2; j++)
					System.out.print(' ');
			}
			System.out.println();
			emptyLeaf /= 2;
			while(localStack.isEmpty()==false)
				globalStack.push( localStack.pop() );
		}
	System.out.println("****......................................................****");
	} 
} 
class LowestComAncestor
{

	public static void main(String[] args) throws IOException
	{
		int value;
		Tree theTree = new Tree();
		theTree.insert(42);
		theTree.insert(25);
		theTree.insert(65);
		theTree.insert(12);
		theTree.insert(37);
		theTree.insert(13);
		theTree.insert(30);
		theTree.insert(43);
		theTree.insert(87);
		theTree.insert(99);
		theTree.insert(9);
		theTree.insert(120);

		System.out.println("Displaying the tree");
		theTree.displayTree();

		Node get1 = theTree.find(43);
		Node get2 = theTree.find(120);
		
		Node getRoot1 = theTree.returnRoot();

		Node LCA1 = theTree.leastCommonAncestor(getRoot1, get1, get2);
	
		System.out.println("The Lowest common ancestor of 43 and 120 is : " + LCA1.item);

		Node get3 = theTree.find(9);
		Node get4 = theTree.find(120);
		
		Node getRoot2 = theTree.returnRoot();

		Node LCA2 = theTree.leastCommonAncestor(getRoot2, get3, get4);
	
		System.out.println("The Lowest common ancestor of 9 and 120 is : " + LCA2.item);

		Node get5 = theTree.find(99);
		Node get6 = theTree.find(120);
		
		Node getRoot3 = theTree.returnRoot();

		Node LCA3 = theTree.leastCommonAncestor(getRoot3, get5, get6);
	
		System.out.println("The Lowest common ancestor of 99 and 120 is : " + LCA3.item);


	} 
} 

OUTPUT:

~/Tree$ java LowestComAncestor 
Displaying the tree
****......................................................****
                                42                                                              
                25                              65                              
        12              37              43              87              
    9      13      30      --      --      --      --      99      
  --  --  --  --  --  --  --  --  --  --  --  --  --  --  --  120  
****......................................................****
The Lowest common ancestor of 43 and 120 is : 65
The Lowest common ancestor of 9 and 120 is : 42
The Lowest common ancestor of 99 and 120 is : 99

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: