Lowest common ancestor without root

Problem

There is a binary tree where each node is having a parent pointer. We need to have an algorithm to find out the lowest common ancestor where two nodes are given, but no root node is given.

Solution

We take one node and follow its parent link till we face null. We keep on putting each node in a hashset. Next we take another node and follow its parent link and keep on checking each node in the hashset. when it finds a match in hashset, that very node is the lowest common ancestor.

Code

import java.util.HashSet;


public class LeastCommonAncestorWithoutRoot
{
 public static void main(String[] args)
 {
  NodeWithParent a=new NodeWithParent(5);
  NodeWithParent b=new NodeWithParent(6);
  NodeWithParent c=new NodeWithParent(7);
  NodeWithParent d=new NodeWithParent(8);
  NodeWithParent e=new NodeWithParent(9);
  a.left=b;
  b.parent=a;
  b.left=c;
  c.parent=b;
  b.right=d;
  d.parent=b;
  d.right=e;
  e.parent=d;
  System.out.println("LCA: "+getLCA(c, e).value);
  
 }
 
 public static NodeWithParent getLCA(NodeWithParent a, 
  NodeWithParent b)
 {
  HashSet<NodeWithParent> table=
    new HashSet<NodeWithParent>();
  while(a!=null)
  {
   table.add(a);
   a=a.parent;
  }
  while(b!=null)
  {
   if(table.contains(b))
    return b;
   b=b.parent;
  }
  return null;
 }

}

class NodeWithParent
{
 public NodeWithParent parent;
 public int value;
 public NodeWithParent left;
 public NodeWithParent right;
 
 public NodeWithParent(int value)
 {
  this.value=value;
 }
}