How to select a binary tree node uniformly at random
The algorithm works just fine.

Note that each node's size field tells you the total number of nodes in the subtree rooted at that node. Throughout this answer, I'm just going to assume that a child's size is zero if the child is null.  Thus, for any node in the tree, we have

this.size == left.size + 1 + right.size


Consider the root of the tree.  If we choose a node of the tree uniformly at random, then it should be in the left subtree with probability left.size/size, it should be the root node with probability 1/size and it should be in the right subtree with probability right.size/size.  By the equation above, these three probabilities add up to&nbsp;1.  If you look at lines 15&ndash;22, the algorithm implements exactly this probability distribution.  It generates a uniform random integer in the range 0 .. size-1.  If this number is in the range 0 .. left.size-1, the algorithm picks a random node from the left subtree; if it's equal to left.size, it picks the root and, otherwise, it picks a random node from the right subtree.

And the argument I gave doesn't depend on the node you consider being the root, so the recursive calls behave as they should.  The algorithm doesn't care about the depth of the nodes: it just recurses down the subtree and chooses subtrees with the correct probability.