LCA = Lowest Common Ancestor
The following code finds the lowest common ancestor in tree of nodes, where a node can have two parents, left and right.
The tree looks like this:
J-K
/ \
E-F-G-H-I
And K and H input, the output is F
public TreeSet<Node> find(Node node, TreeSet<Node> nodeSet) {
nodeSet.add(node);
if (node.getLeft() != null) {
find(node.getLeft(), nodeSet);
}
if (node.getRight() != null) {
find(node.getRight(), nodeSet);
}
return nodeSet;
}
which is called here:
TreeSet<Node> nodeList1 = new TreeSet<Node>();
TreeSet<Node> nodeList2 = new TreeSet<Node>();
nodeList1 = find(node1, nodesList1); // node1 = K
nodeList2 = find(node2, nodesList2); // node2 = H
Iterator iterator = nodeList1.descendingIterator();
while (iterator.hasNext()){
Node node = (Node) iterator.next();
if(nodeList2.contains(node)){
return node.getValue();
}
}
and a Node
looks like you'd expect and implements comparable.
Is my implementation O(n), I think it is, but can it be improved?
The relvant snippet of Node
:
class Node implements Comparable<Node> {
private String value;
private Node left;
private Node right;
@Override
public int hashCode() {
return this.getValue().hashCode();
}
@Override
public int compareTo(Node o) {
return this.getValue().compareTo(o.getValue());
}
node1
is a child ofnode2
(ornode2
is a child ofnode1
) \$\endgroup\$