[Java] BST element distance - parent pointer

Well, that's a bit anticlimactic. After playing with the other approaches, the one that initially gave me the most pain was also quite fast to implement as soon as the AHA! moment came.

However spoiler alert: the results are quite disappointing.


Getting to our quite deserved meat, here is the idea; if we have a tree with parent pointers, we can use them to walk the distance between two elements as follows:

• navigate from the root to the first element and keep track of its node and the travelled distance
• if the element is not there, we just return -1, otherwise we repeat the same operations for the second element
• if it is not there, again return -1, otherwise starting from the deepest (longest path) element, we navigate up the tree reducing the total path length for that element
• we check if the two nodes are equal, or if they share the same parent, or if we are the root. If not, we repeat the last step but this time maybe the deepest element is the other one so we will alternate
• keep doing this until the above condition is satisfied; that means we are at the lowest common ancestor and then the total distance is the sum of the remaining paths from this point to the two elements

The reason why this is a bit disappointing is that the overall time has not improved at all from the previous approaches. Yes we are still not using the extra lists space and the operations are a bit more condensed, but for time we have:

• finding both elements is O(n) as usual
• navigating up from both elements is ... still O(n). Since we are navigating up and stopping at the root or a match, worst case is our ugly single branch tree and one element is the leaf and the other one is in the middle of the branch. We will navigate the tree halfway up before stopping, but that's still order n because sometimes the big O giveth and other times it taketh away :(

What is interesting though is that if the tree is balanced perfectly (log n height) we have of course better performance but just because of that since the overall result would not change between the three approaches!

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.