[Java] BST element distance - lowest common ancestor

So I was thinking about the parent pointer approach to find the distance between to elements in a binary search tree and avoiding using the path lists approach, which means finding the lowest common ancestor; that's the lowest node in the tree that is common to both paths to the two elements.
If the elements are one the child of the other, then it will be equal to the parent, otherwise it will either be the root if the elements are on completely different branches or the divergence node if the elements are in the same subtree.

Then I got down to coding and when I got to the LCA logic, finally, ... I did not use the parent pointer yet again :(


The idea this time was: once I know which is the branching element between the two, I can just walk from that one down to both elements and sum up the paths to get my distance; no need for parent pointers here.

Well, the meat of this solution then is simply: how do I find the LCA?

For me it goes as follows, starting from the given node (initially the root) check in sequence:

• is the current node one of the two elements I'm looking for? If yes, that's also the LCA because the other one must be its child, return
• are both elements on the left side of the current node? Then search for the LCA in the left subtree
• are both elements on the right side of the current node? Then search for the LCA in the right subtree
• otherwise the current node is also the branching element, return it

BUT, there is a small catch: we are still not completely sure that both elements are in the tree. The LCA we found is the logical one according to the tree structure ASSUMING both elements are there, but maybe only one is there. The idea now is to either verify first if the tree contains both elements, or to navigate to both elements starting from the LCA and verify we find both of them.

So, we got rid of the extra space used by the path lists and in terms of time we now have:

• find the LCA is O(n). Example if the tree is a single branch, only one of the two elements is in the tree and it's also the leaf
• verify that both elements are in the tree starting from the LCA is O(n). Example if the LCA is the root and the other element is either the leaf on a single branch tree or not in the tree at all

It means we're happier than before because we got rid of the extra structures and removed some operations, but the overall time has not changed at all.

Also, I agree there are lots of optimisations possible in the uploaded code, but remember that's just a playground, not real production code that, if you're lucky, gets days (well ok, depends on many factors) of time before getting delivered while the online exercises allow from 1 to 2 hours tops to be understood, solved and tested.

While I keep playing with it I will update it as well, don't worry.

The parent pointer approach can be found here instead.

You can check the code and a sample JUnit test source on my Gist. The full project was developed with IntelliJ and Gradle using JDK 8.