Solution: Binary Tree Right Side View

Statement#

You are given a root of a binary tree that has n number of nodes. You have to return the right-side view in the form of a list.

A right-side view of a binary tree is the data of the nodes that are visible when the tree is viewed from the right side.

Constraints:

• $0 \leq$ n $\leq 100$
• $-100 \leq$ Node.data $\leq 100$

Solution#

To return the list of the right-side view of the tree, we will apply a recursive depth-first search (DFS) approach. Our main function will first check if the root is NULL, in which case it returns an empty list. If the root is not NULL, we will initialize an empty list, rside, which will store the data of the tree’s rightmost nodes. Since we need only one right-side element at each level, the index of rside list will be maintained to keep track of these node values.

The recursive DFS() function will take three arguments as input, which are rside, node, and level, and check whether rside's length is equal to the current tree level. If this is TRUE, then add node's value to the list.

Next, we’ll iterate over node to check for any children. Here, the right child of the node will be visited first. If the child is not NULL, we’ll recursively call the DFS() function on that child, along with incrementing the level of the tree by 1. The purpose of visiting the right child first is that the rightmost elements of a level will be appended to the rside list, thereby increasing its length.

Finally, after completing the depth-first search, we will return the rside list, containing the right-side view of the tree.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s look at the code for this solution below:

Time complexity#

The time complexity will be $O(n)$, where $n$ is the number of nodes because each node is traversed once.

Space complexity#

The space complexity of this solution is $O(h)$, where $h$ is the tree’s height.