Coding Challenge: Binary Tree View from the Right Side

We are continuing our coding challenge series with a problem involving binary trees. In our previous article, we used a Depth First Search approach to traverse a 2D grid and come to a solution regarding the number of islands in the grid. A DFS approach with trees involves traversing down the entire length of a branch before recursively or iteratively traversing the other branches of the tree. A BFS approach is an iterative level order traversal of the tree where we go left to right as shown in the diagram above. Deciding on a DFS or BFS traversal is tricky when approaching problems but that’s why we practice and create the mental connection to these approaches.

Today’s problem involves printing the side view of a binary tree. For my solution, we will be looking at the right-hand view but switching to the left-hand view only takes some small adjustments in our code.

The Problem:

Given the root of a binary tree, return the view from the right-hand side of the tree. See the example image below:

The expected return for the above input is a list of values [1, 3, 4]. 2 and 5 are not seen from the right-hand view as they are being covered by more superficial nodes (3 & 4).

I’ve already hinted at the beginning that this problem involves a Breadth-First Search Approach. If we just intuitively talk through the problem. We want to…

• Go down each level
• Determine all the values on that level
• Take the last value on that level and add it to our results list.
• Once we reach a level that has no values we can assume we have traversed the entire tree as there are no more nodes.

Feel free to use the above gist to play around, create your own trees and test my solution. Most of the logic is stored in the previousLevel helper function. In this function, I created a temporary list to store the next level of the binary tree. We take the last value in our temp list and add it to results as that node is the rightmost node on that level. Finally, we reassign the previousList variable to our temp list so that we can continue iterating through the levels of our tree. The case where our loop ends is when there are no nodes in our temporary list and when this condition is met we can return our results array containing the values from the right-hand view.

This approach has a time complexity of O(n) as we are visiting every node and space complexity of O(n) as we are using arrays to store values.

Thank you for joining me in this weeks article and feel free to leave your own approaches to this problem!