language: Java (sun-jdk-1.7.0_10)
date: 592 days 13 hours ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

/*
 * 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);
    }
}
 
Main.java:13: class LCA is public, should be declared in a file named LCA.java
public class LCA {
       ^
1 error