   Type like pro

# 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)
{
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;
}
}        ```