[LC Walkthrough] 199. Binary Tree Right Side View

Hello world! This is the sixth article of LeetCode Walkthrough.

Today, I’ll be writing about 199. Binary Tree Right Side View. It is the sixth question of February LeetCoding Challenge 2021.

For this problem, given a binary tree, we need to return the values of the nodes you can see from the right side of the tree (ordered from top to bottom).

For example, let say the given binary tree looks like this:

We would be returning [1, 3, 4] as that’s the value we see from the right side of the tree.

If you look closely, you can probably figure out that they want us to return the rightmost node on each level of the tree. I decided to use Breath-first Search (BFS) as Level-order traversals can be easily done with it. If you don’t have the template for BFS remembered, I highly recommend you to memorize it as it comes really handy (same goes for DFS).

With that in mind, we can come up with the following code:

Let us run a test case:

The time complexity of this solution is O(n) where n = # of nodes in the tree. During level-order traversal, we will eventually visit every node in the tree.

The space complexity of this solution is O(n) where n = # of nodes in the tree. During level-order traversal, the queue will grow to the size of each level. It will grow to the biggest size if the given binary tree is a perfectly balance tree which has (n/2)-1 nodes on its last level. (n/2)-1 can be simplified to n, hence O(n) space complexity.

Thanks for reading!