LCA = Lowest Common AncestorThe 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-IAnd K and H input, the output is Fpublic 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 = KnodeList2 = find(node2, nodesList2); // node2 = HIterator 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());        }
Lowest common ancestor in recursive tree traversal
java;optimization;algorithm;recursion;tree
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().AlgorithmI 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...ComplexityYour 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 = KnodeList2 = find(node2, nodesList2); // node2 = HIterator iterator = nodeList1.iterator();Node minimalNode = nullwhile (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)\$.