Lowest common ancestor in recursive tree traversal 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&lt;Node&gt; find(Node node, TreeSet&lt;Node&gt; 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&lt;Node&gt; nodeList1 = new TreeSet&lt;Node&gt;();
TreeSet&lt;Node&gt; nodeList2 = new TreeSet&lt;Node&gt;();
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&lt;Node&gt; {

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