[Java] Binary tree right side view

Given a binary tree, return a list containing all elements we would side at each level if we were looking at the tree from the right side.

Example

  1

 /\

 2 3

return 1,3 since 2 is hidden by 3 on its level.

We can solve this with a BFS or even recursively.

Using BFS, we add nodes to a queue and insert a marker to indicate the end of a level.

We then walk on all nodes and look in the queue for the next. If it is a marker, we add ourselves to the list and reinsert the marker in the queue ONLY if there are other nodes left (our children or children of nodes before us).

This works in O(N) time and uses O(2^logN) space which is O(N) in worst case (we have a full tree and add all nodes at the lowest level in the queue).

Using recursion, we need a bit of adjustment as we must track the deepest level we reached during our exploration, we can then do a recursion that visits the right side first.

At each call, we compare the level we are with the deepest level we visited (global variable or int wrapper). If we are equal to that level, we are the first to reach it so we add ourselves to the result, then increase this maximum value.

We then invoke the recursion on our right child before the left.

This also works in O(N) time and still uses O(N) space in worst case (the tree is a branch all in one direction).

Notice the worst case for space is different between BFS and DFS.

You can check my implementation of rightSideView on my Gist along with some tests in RightSideViewJTests.