First Common Ancestor

public interface FirstCommonAncestor { 

/** 
* Given two nodes of a tree, 
* method should return the deepest common ancestor of those nodes. 
* 
* A 
* / \ 
* B C 
* / \ \ 
* D E M 
* / \ 
* G F 
* 
* commonAncestor(D, F) = B 
* commonAncestor(C, G) = A 
*/ 

public Node commonAncestor(Node nodeOne, Node nodeTwo) 
{ 

} 
} 

class Node { 

final Node parent; 
final Node left; 
final Node right; 
final data;

public Node(Node parent, Node left, Node right, data) { 
this.parent = parent; 
this.left = left; 
this.right = right; 
this.data = data 
} 

boolean isRoot() { 
return parent == null; 
} 
}

Using a, actually two stacks to store the node while traversing the tree from each node to the root. After that, pop the node and check if the next node in both stacks are equal (stackOne.peek() == stackTwo.peek()), if not, or if one of the stacks is empty, which means the last node in the empty stack is an ancestor/parent of the other stack, return the node.

My code doesn't specifically "implement" the interface for the sake of testing, but the algorithm is the same.

import java.util.*;
public class FirstCommonAncestor {
 public Node commonAncestor(Node nodeOne, Node nodeTwo) {
  if (nodeOne == nodeTwo)
   return nodeOne.parent;
  Stack stackOne = new Stack ();
  Stack stackTwo = new Stack ();
  Node one = nodeOne;
  Node two = nodeTwo;
  while(one != null && two != null) {
   stackOne.push(one);
   stackTwo.push(two);
   one = one.parent;
   two = two.parent;
  }
  while (one != null) {
   stackOne.push(one);
   one = one.parent;
  }
  while (two != null) {
   stackTwo.push(two);
   two = two.parent;
  }
  while(!stackOne.isEmpty() && !stackTwo.isEmpty()) {
   Node head1 = stackOne.pop();
   stackTwo.pop();
   if ((stackOne.isEmpty() || stackTwo.isEmpty()) || stackOne.peek() != stackTwo.peek()) {
    return head1;
   }
  }
   
  return null;
 }
}
public class Node {
 Node parent; 
 Node left; 
    Node right; 
    Object data;

 public Node(Object data) {
  this.parent = null;
  this.left = null;
  this.right = null;
  this.data = data;
 }

 public Node(Node parent, Node left, Node right, Object data) { 
  this.parent = parent; 
  this.left = left; 
  this.right = right; 
  this.data = data; 
  } 

 boolean isRoot() { 
  return parent == null; 
 } 

}