/* * 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 ancestors = new HashSet(); 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); } }