fork(1) download
copy 
  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5. package javaprojects;
  6.  
  7. import java.util.HashSet;
  8. import java.util.Set;
  9.  
  10. /**
  11.  *
  12.  */
  13. public class LCA {
  14.  
  15.     private class Node {
  16.  
  17.         int data;
  18.         Node[] children = new Node[0];
  19.         Node parent;
  20.  
  21.         public Node() {
  22.         }
  23.  
  24.         public Node(int v) {
  25.             data = v;
  26.         }
  27.  
  28.         @Override
  29.         public boolean equals(Object other) {
  30.             if (this.data == ((Node) other).data) {
  31.                 return true;
  32.             }
  33.             return false;
  34.         }
  35.     }
  36.     private Node root;
  37.  
  38.     public LCA() {
  39.         root = new Node(3);
  40.  
  41.         root.children = new Node[4];
  42.         root.children[0] = new Node(15);
  43.         root.children[0].parent = root;
  44.         root.children[1] = new Node(40);
  45.         root.children[1].parent = root;
  46.         root.children[2] = new Node(100);
  47.         root.children[2].parent = root;
  48.         root.children[3] = new Node(10);
  49.         root.children[3].parent = root;
  50.  
  51.         root.children[0].children = new Node[3];
  52.         root.children[0].children[0] = new Node(22);
  53.         root.children[0].children[0].parent = root.children[0];
  54.         root.children[0].children[1] = new Node(11);
  55.         root.children[0].children[1].parent = root.children[0];
  56.         root.children[0].children[2] = new Node(99);
  57.         root.children[0].children[2].parent = root.children[0];
  58.  
  59.         root.children[2].children = new Node[2];
  60.         root.children[2].children[0] = new Node(120);
  61.         root.children[2].children[0].parent = root.children[2];
  62.         root.children[2].children[1] = new Node(33);
  63.         root.children[2].children[1].parent = root.children[2];
  64.  
  65.         root.children[3].children = new Node[4];
  66.         root.children[3].children[0] = new Node(51);
  67.         root.children[3].children[0].parent = root.children[3];
  68.         root.children[3].children[1] = new Node(52);
  69.         root.children[3].children[1].parent = root.children[3];
  70.         root.children[3].children[2] = new Node(53);
  71.         root.children[3].children[2].parent = root.children[3];
  72.         root.children[3].children[3] = new Node(54);
  73.         root.children[3].children[3].parent = root.children[3];
  74.  
  75.         root.children[3].children[0].children = new Node[2];
  76.         root.children[3].children[0].children[0] = new Node(25);
  77.         root.children[3].children[0].children[0].parent = root.children[3].children[0];
  78.         root.children[3].children[0].children[1] = new Node(26);
  79.         root.children[3].children[0].children[1].parent = root.children[3].children[0];
  80.  
  81.         root.children[3].children[3].children = new Node[1];
  82.         root.children[3].children[3].children[0] = new Node(27);
  83.         root.children[3].children[3].children[0].parent = root.children[3].children[3];
  84.     }
  85.  
  86.     private Node findNode(Node root, int value) {
  87.         if (root == null) {
  88.             return null;
  89.         }
  90.         if (root.data == value) {
  91.             return root;
  92.         }
  93.         for (int i = 0; i < root.children.length; i++) {
  94.             Node found = findNode(root.children[i], value);
  95.             if (found != null) {
  96.                 return found;
  97.             }
  98.         }
  99.         return null;
  100.     }
  101.  
  102.     public void LCA(int node1, int node2) {
  103.         Node n1 = findNode(root, node1);
  104.         Node n2 = findNode(root, node2);
  105.         Set<Node> ancestors = new HashSet<Node>();
  106.         while (n1 != null) {
  107.             ancestors.add(n1);
  108.             n1 = n1.parent;
  109.         }
  110.         while (n2 != null) {
  111.             if (ancestors.contains(n2)) {
  112.                 System.out.println("Found common ancestor between " + node1 + " and " + node2 + ": node " + n2.data);
  113.                 return;
  114.             }
  115.             n2 = n2.parent;
  116.         }
  117.     }
  118.  
  119.     public static void main(String[] args) {
  120.         LCA tree = new LCA();
  121.         tree.LCA(33, 27);
  122.     }
  123. }
  124.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:13: class LCA is public, should be declared in a file named LCA.java
public class LCA {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/gpO3s
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!