There is a Warning section for this:

Warning

I added some tests to ensure that when insert(x) and remove(x) and contains(x) are called that you only work on the relevant portion of the tree. If you go down the wrong tree on these test cases, you could potentially loop forever (until the Code timeout kills you). Because of the way that I crafted these test cases, you also need to make sure that you wrote depth() and count() recursively rather than somehow using the traversal methods: inorder(), preorder(), postorder(), or iteratively walking left and right.

However, I am also having the same issue and I've implemented depth() and count() recursively.

I was also getting some test cases failing randomly but that was because my code was not completely right for the case of removing a head node when it has subtrees (as it needs to get the leftmost node of its right tree - as explained at http://www.algolist.net/Data_structures/Binary_search_tree/Removal), after I did that part I am no longer getting those random failures.

I was having this same thing. The issue is that I was always returning a new EmptyNode while this test is expecting it to be the same EmptyNode from the tail node.

The problem is too complex and the solution is not a result of a thought construction but instead from trial and error