Lowest common ancestor in recursive tree traversal

Question

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());
 }

• rolfl: You use the words "finds the lowest common ancestor in tree of nodes" but the picture you draw is not a tree, and nowhere in your code do you have a 'root'... your 'find' method just builds a set of children, not ancestors. Does your code work?
• NimChimpsky: @rolfl ok, what would you call the picture ? children/ancestors semantics ? Yes the code works.
• rolfl: @NimChimpsky - A tree does not contain cycles... yet your picture shows a cycle. Since your node does not contain a 'parent' pointer, you cannot find the 'parent' of either of your nodes, so you cannot scan 'up' the tree. And, since you do not show us where you keep the 'root', there is no apparent way to find the 'ancestors' of either node. Which means your code will only work if node1 is a child of node2 (or node2 is a child of node1)
• NimChimpsky: @rolfl left and right are parents, the root node is available... I just haven't used it.
• rolfl: This data structure is not a tree.

Answer 1

Naming - the method find(Node, TreeSet<Node>) implies it will find the Node inside the TreeSet, which, of course it doesn't - a better name might be buildNodeParents or something like that.

Also, your Node has getLeft() and getRight(). In most implementations of a node tree, left and right implied the node's children. In your case, for clarity - I would have called those methods getLeftParent() and getRightParent().

Algorithm

I assume your node implements Comparable (because you are using descendingIterator()) it would be useful if you've added that code, so complexity will be more easily calculated - how does it know if it is lower than another node? Maybe I've missed the correct definition for 'lowest' from your description? The sample tree you've shown is not very clear...

Complexity

Your algorithm's complexity is \$O(n) * (O(i) + O(f))\$ where n is the number of the nodes in your tree, i is the complexity of inserting a single value to the TreeSet (add()), and f is the complexity of finding a single value to the TreeSet (contains()). Assuming the Node.compareTo is of complexity \$O(1)\,ドル AFAIK TreeSet complexity is \$O(log(n))\$.

This means that your algorithm's complexity is at least \$O(n \cdot log(n))\$

To achieve complexity of \$O(n)\,ドル I would choose a HashSet (which has complexity \$O(1)\$ for inserting and finding elements) over TreeSet. Then in the last part of the algorithm, instead of returning the first mutual ancestor, return the lowest mutual ancestor:

HashSet<Node> nodeList1 = new HashSet<Node>();
HashSet<Node> nodeList2 = new HashSet<Node>();
nodeList1 = find(node1, nodesList1); // node1 = K
nodeList2 = find(node2, nodesList2); // node2 = H
Iterator iterator = nodeList1.iterator();
Node minimalNode = null
while (iterator.hasNext()){
 Node node = (Node) iterator.next();
 if(nodeList2.contains(node)){
 if (minimalNode == null || node.compareTo(minimalNode) < 0) {
 minimalNode = node;
 }
 }
}
return minimalNode;

This has, again the same complexity of \$O(n) * (O(i) + O(f))\,ドル but in this case \$O(i)\$ and \$O(f)\$ are \$O(1)\$ - so the total complexity is \$O(n)\$.

• Uri Agassi: Added a suggestion for O(n)
• rolfl: @UriAgassi can you figure out how the ancestor of two nodes is somewhere in the intersection of the descendants of two nodes?
• Uri Agassi: @NimChimpsky - no, because LinkedList has a find complexity of O(n) - this would make for a total complexity of O(n^2). @rolfl - you can see that my second passage - my assumption was that getLeft() and getRight() are actually getLeftParent() and getRightLeft()...
• NimChimpsky: @UriAgassi oh yes of course. Thanks muchly.

Answer 2

You seem to be have a few misconceptions, as @rolfl points out.

First, the data structure you have described and illustrated does not fit the definition of a tree. Rather, I would characterize your data structure as a graph of maximum in-degree 2.

Second, you seem to be under the impression that the TreeSet internally contains a tree that resembles part of your original graph. Actually, a TreeSet is nothing more than a SortedSet; the fact that the SortedSet is implemented by using a tree internally is irrelevant to you. nodeList1.descendingIterator() does not produce an iterator that walks from root to leaf. Rather, it yields nodes reverse-sorted according to the value contained in the node.

As a result, the code does not work.

Answer 3

Just a minor note: you could add the Node type to the iterator which would make the casting unnecessary and would remove the compiler warning:

Iterator<Node> iterator = nodeList1.descendingIterator();
while (iterator.hasNext()) {
 Node node = iterator.next();