1 /**
  2  * Author:  Elvis Montero
  3  * URL:     www.elvismontero.com
  4  * License: This code is licensed under the Creative Commons Attribution
  5  *          Share-Alike License v3.0 or any other later version.
  6  */
  7 
  8 package progpraxis;
  9 
 10 import java.util.Stack;
 11 
 12 public class LowestCommonAncestor {
 13 
 14     public static void main(String[] args){
 15         Node four = new Node(null, null, 4);
 16         Node seven = new Node(null, null, 7);
 17         Node thirteen = new Node(null, null, 13);
 18 
 19         Node six = new Node(four, seven, 6);
 20         Node fourteen = new Node(thirteen, null, 14);
 21 
 22         Node one = new Node(null, null, 1);
 23         Node three = new Node(one, six, 3);
 24 
 25         Node ten = new Node(null, fourteen, 10);
 26         Node eight = new Node(three, ten, 8); // root
 27 
 28         Stack<Node> stack = new Stack<Node>();        
 29         traverse(eight, stack);
 30 
 31         String lowest = getLowestCommonAncestor(four, seven);
 32         System.out.println(lowest);
 33 
 34         lowest = getLowestCommonAncestor(four, ten);        
 35         System.out.println(lowest);
 36 
 37         lowest = getLowestCommonAncestor(one, four);
 38         System.out.println(lowest);
 39 
 40         lowest = getLowestCommonAncestor(one, three);
 41         System.out.println(lowest);
 42 
 43         lowest = getLowestCommonAncestor(three, six);
 44         System.out.println(lowest);
 45     }
 46 
 47     // Traverse the tree in DFS fashion and find the path for every node
 48     static void traverse(Node node, Stack<Node> stack){
 49         stack.push(node);
 50         
 51         if(node.getRight() != null)
 52             traverse(node.getRight(), stack);
 53         
 54         if(node.getLeft() != null)
 55             traverse(node.getLeft(), stack);
 56 
 57         StringBuilder path = new StringBuilder();
 58         for(Node n : stack)
 59             path.append(n).append(" ");
 60         node.setPath(path.toString().trim());
 61 
 62         stack.pop();
 63         return;
 64     }
 65 
 66     // Compare each node's path and find the lowest common ancestor
 67     static String getLowestCommonAncestor(Node m, Node n){
 68         String longerPath  = (m.getPath().length() > n.getPath().length()) ? m.getPath() : n.getPath();
 69         String shorterPath = (longerPath.equals(m.getPath())) ? n.getPath() : m.getPath();
 70 
 71         String[] lpElements  = longerPath.split(" ");
 72         String[] spElements  = shorterPath.split(" ");
 73 
 74         String lowest = "";
 75         for(int i = 0; i < spElements.length; i++)
 76                 if(spElements[i].equals(lpElements[i]))
 77                     lowest = spElements[i];
 78         
 79         return lowest;
 80     }
 81 
 82 }
 83 
 84 // Class representing our tree's nodes
 85 class Node{
 86     private Node left;
 87     private Node right;
 88     private int value;
 89     private String path;
 90 
 91     public Node(Node left, Node right, int value){
 92         this.left = left;
 93         this.right = right;
 94         this.value = value;
 95     }
 96 
 97     public Node getLeft(){
 98         return left;
 99     }
100 
101     public Node getRight(){
102         return right;
103     }
104 
105     public void setLeft(Node left){
106         this.left = left;
107     }
108 
109     public void setRight(Node right){
110         this.right = right;
111     }
112 
113     public void setPath(String path){
114         this.path = path;
115     }
116 
117     public String getPath(){
118         return path;
119     }
120 
121     @Override
122     public String toString(){
123         return String.valueOf(value);
124     }
125 }