[Java] Find deepest node of tree

Given the root of a binary tree, find any of the deepest nodes.

This problem is similar to finding the depth of a tree, only this time we collect a pair (node, depth) and when we recurse on each node, we pick from it the node that was deepest among the two left and right children.

We can do this in O(N) time and space worst case (tree is a branch).

You can check my implementation of getDeepestNode on my Gist along with some tests in GetDeepestNodeJTests.