[Java] Collect all nodes at given depth in binary tree

Given a binary tree, return all nodes at a given depth.

We could do a level traversal with a queue BFS style, adding markers in the queue to determine when a new level is reached. Once we arrive at the desired level, we add all nodes between the current marker and the next to the solution.

Complexity is O(N) time and space in worst case. Although for BFS space worst case happens when tree is balanced (all nodes at a certain level are added to the queue).

We can also do DFS which has O(N) time and space complexity again, but worst case for space in DFS is when tree is a branch (call stack is the whole tree).

If we do BFS we can iteratively collect the result, if we do recursive DFS, we need to pass in input a structure where we will collect the result.

The order of elements in the result can be controlled by deciding whether to move left or right first.

You can check my implementation of getAllValuesAtDepth on my Gist along with some tests in GetAllValuesAtDepthJTests.