I've been reading about the Lowest Common Ancestor algorithm on top coder and I can't understand why the RMQ algorithm is involved - the solution listed there is insanely complicated and has the following properties:
My solution: given 2 integer values, find the nodes through a simple preorder traversal. Take one of the nodes and go up the tree and store the path into a Set. Take the other node and go up the tree and check each node as I go up: if the node is in the Set, stop and return the LCA. Full implementation.
So given these two choices, is the algorithm on Top Coder better and if yes, why? That's what I can't understand. I thought O(log n) is better than O(sqrt(n)).
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);
}
}
The LCA algorithm works for any tree (not necessarily binary and not necessarily balanced). Your "simple algorithm" analysis breaks down since tracing a path to a root node is actually O(N) time and space instead of O(log N)