/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javaprojects;
import java.util.HashSet;
import java.util.Set;
/**
*
*/
public class LCA {
private class Node {
int data;
Node[] children = new Node[0];
Node parent;
public Node() {
}
public Node(int v) {
data = v;
}
@Override
public boolean equals
(Object other
) { if (this.data == ((Node) other).data) {
return true;
}
return false;
}
}
private Node root;
public LCA() {
root = new Node(3);
root.children = new Node[4];
root.children[0] = new Node(15);
root.children[0].parent = root;
root.children[1] = new Node(40);
root.children[1].parent = root;
root.children[2] = new Node(100);
root.children[2].parent = root;
root.children[3] = new Node(10);
root.children[3].parent = root;
root.children[0].children = new Node[3];
root.children[0].children[0] = new Node(22);
root.children[0].children[0].parent = root.children[0];
root.children[0].children[1] = new Node(11);
root.children[0].children[1].parent = root.children[0];
root.children[0].children[2] = new Node(99);
root.children[0].children[2].parent = root.children[0];
root.children[2].children = new Node[2];
root.children[2].children[0] = new Node(120);
root.children[2].children[0].parent = root.children[2];
root.children[2].children[1] = new Node(33);
root.children[2].children[1].parent = root.children[2];
root.children[3].children = new Node[4];
root.children[3].children[0] = new Node(51);
root.children[3].children[0].parent = root.children[3];
root.children[3].children[1] = new Node(52);
root.children[3].children[1].parent = root.children[3];
root.children[3].children[2] = new Node(53);
root.children[3].children[2].parent = root.children[3];
root.children[3].children[3] = new Node(54);
root.children[3].children[3].parent = root.children[3];
root.children[3].children[0].children = new Node[2];
root.children[3].children[0].children[0] = new Node(25);
root.children[3].children[0].children[0].parent = root.children[3].children[0];
root.children[3].children[0].children[1] = new Node(26);
root.children[3].children[0].children[1].parent = root.children[3].children[0];
root.children[3].children[3].children = new Node[1];
root.children[3].children[3].children[0] = new Node(27);
root.children[3].children[3].children[0].parent = root.children[3].children[3];
}
private Node findNode(Node root, int value) {
if (root == null) {
return null;
}
if (root.data == value) {
return root;
}
for (int i = 0; i < root.children.length; i++) {
Node found = findNode(root.children[i], value);
if (found != null) {
return found;
}
}
return null;
}
public void LCA(int node1, int node2) {
Node n1 = findNode(root, node1);
Node n2 = findNode(root, node2);
Set<Node> ancestors = new HashSet<Node>();
while (n1 != null) {
ancestors.add(n1);
n1 = n1.parent;
}
while (n2 != null) {
if (ancestors.contains(n2)) {
System.
out.
println("Found common ancestor between " + node1
+ " and " + node2
+ ": node " + n2.
data); return;
}
n2 = n2.parent;
}
}
public static void main
(String[] args
) { LCA tree = new LCA();
tree.LCA(33, 27);
}
}