Lowest common ancestor

Problem

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

Solution

A node X has left subtree and right subtree. One or both of them can be null. If the two given nodes A and B are not present in any of the subtrees, then X can never be reached from A and B following the parent link. On the other hand if A and B are both on the right subtree or in the left subtree, then the node X is common ancestor, but not the lowest one. Because if A and B are both present in the right subtree of X, then at least root of the right subtree of X is a better candidate for being lowest common ancestor.

So lowest common ancestor will be a node which has one given node on its left and the other one on its right. Or the node itself is one of the given node and another one is in its subtree.

In this solution we have a recursive function which tries to find the count of found nodes in a node’s left and right subtree. When the numbers are 1 on left and 1 on right then the given node is the answer. When the count is 1 in either side and the node itself is one of the given node then also the node is the lowest common ancestor, else it recursively calls the function to its left and right children and return the sum of them.

Code

package problems;

public class LowestCommonAncestor
{

 /**
  * @param args
  */
 public static void main(String[] args)
 {

  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(8);
  Node g = new Node(6);
  Node h = new Node(7);
  a.left = b;
  a.right = c;
  b.left = d;
  c.left = e;
  c.right = f;
  f.left = g;
  f.right = h;
  LCA(a, c, h);
  System.out.println(LCANode.value);
  
 }

 static Node LCANode = null;

 public static int LCA(Node currentNode, Node n1, Node n2)
 {
  if (currentNode == null)
   return 0;
  int currentValue = 0;
  if (currentNode == n1 || currentNode == n2)
   currentValue = 1;
  int leftValue = LCA(currentNode.left, n1, n2);
  int rightValue = LCA(currentNode.right, n1, n2);
  if ((currentValue == 1 && leftValue == 1)
     ||(currentValue == 1 && rightValue == 1)
     ||(leftValue == 1 && rightValue == 1))
  {
   LCANode = currentNode;
   return 2;
  }
  return currentValue + leftValue + rightValue;

 }

}