Find common parent in a binary search tree in Java

This is a very famous question that many already are aware of. But I wanted to give a comprehensive working program in java to implement this with illustration. Consider the following binary tree which infact is a binary search tree.

The idea is very simple. For the first node traverse up till you reach root, while doing so, put the nodes in a hash set. Then do the same for the second node ie, try to traverse towards the root. Amidst doing that search for the existence of this node in the hash set we already created for the first traversal.

The place where those two nodes matches will be the common node. For any two nodes in a tree, there will be at least one common node which will be the root. I have given two examples below. One having a node other than root as the common parent and the other with root as the common parent.

The green line shows the traversal of first node path. Red shows the second node's path. The intersection or the common parent is shown in a blue circle.

Now for the Java source.

package dsa.tree;

import java.util.HashSet;
import java.util.Set;

public class FindCommonNode {
 private Node n1,n2;
 
 public static void main(String args[]){
  FindCommonNode nodeFinder = new FindCommonNode();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  System.out.println("Common Parent : "+commonParent.data);
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(45);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  Set<Node> firstNodeAddrSet = new HashSet<Node>();
  //Traverse till root
  while(node1!=null){
   firstNodeAddrSet.add(node1);
   node1 = node1.parent;
  }
  while(!firstNodeAddrSet.contains(node2) && node2!=null){
   node2 = node2.parent;
  }
  return node2;
 }
}

The implementations for Tree and BinarySearchTree can be found here.

Cheers,
Bragaadeesh.