[Java] Find second largest element in BST

Easy question: given a BST, find the second largest element in there.

This can be done in many ways, the most efficient one uses constant O(1) space and O(N) worst case time (tree is unbalanced).

The idea is to walk the tree until we find the biggest element (the one all the way to the right), then check if that node has children. If not, then the second biggest must be his parent; if yes, then the second biggest node is in the left subtree, all the way to the right there. If no right node exists, then it is the left children of the biggest node we found.

My implementation uses the parent pointers, but this can be done all the same without it, by simply tracking an additional node during the looping.

You can check my implementation of getSecondBiggestElement on my Gist along with some test cases in BSTJTests.