Least Common Ancestor without using a parent node in java

We already saw how to find the Least Common Ancestor for a binary tree. The problem gets a bit tricky when the node structure is like this.

class Node {
  Node left;
  Node right;
  int data;
 }

If you look at the above structure, there are no parent nodes and the given tree is not a Binary Search Tree which makes the problem all the more complicated.
To attack this problem we need to follow the below steps.

1. Find the path of the first node using in-order traversal - Cost: O(n)
2. Find the path of the second node using in-order traversal - Cost: O(n)
3. Put the nodes of the first path in a set - Cost: O(logn)
4. For each node in the second path check if it exists in the first path. The matching one would be the Least Common Ancestor - Cost: O(logn)

The total cost for this program would be - O(n) + O(n) + O(logn) + O(logn) = O(n).

Now for the java code. I am going to use the Trace Algorithm from the previous post for this solution to make life easier. Hope you were able to learn something.

package dsa.tree;

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

/**
 * Program to find the Least Common Ancestor without
 * for a Binary Tree (Not a BST). The Node does not have
 * a parent pointer. The direction of the tree is one sided
 * @author Braga
 *
 */
public class LCSBinaryTree {
 private Node n1,n2;
 
 public static void main(String args[]){
  LCSBinaryTree nodeFinder = new LCSBinaryTree();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  if(commonParent == null){
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is null");
  }else{
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is "+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(76);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  TracePath pathTracer = new TracePath();
  
  /**
   * If either of the nodes is root, then there is no common
   * parent
   */
  if(node1.equals(t.getRoot()) || node2.equals(t.getRoot())){
   return null;
  }
  //Using the path tracer, find the path of two nodes in 2*O(n) time.
  Stack<Node> path1 = pathTracer.trace(t, node1);
  Stack<Node> path2 = pathTracer.trace(t, node2);
  
  //All that is left to do is to find the common parent now.
  Set<Node> firstPath = new HashSet<Node>();
  for(Node iNode:path1){
   firstPath.add(iNode);
  }
  while(!path2.isEmpty()){
   Node currentNode = path2.pop();
   if(firstPath.contains(currentNode)){
    if(!path2.isEmpty() && firstPath.contains(currentNode = path2.peek())){
     return path2.peek();
    }
    return currentNode;
   }
  }
  return null;
 }
}
//SAMPLE OUTPUTS
//Common Parent for 887 and 334 is 43
//Common Parent for 43 and 334 is null
//Common Parent for 6 and 334 is 43
//Common Parent for 76 and 334 is 46

Cheers,
Bragaadeesh.