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

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)\$.

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