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

Start the DFS traversal from the tree’s root with an initial depth 0. As you traverse from the parent node to its child nodes, increment the depth by 1 for each level down the tree. This is done by passing incremented depth to the recursive DFS calls for child nodes. When you visit a node, you check if this depth is being visited for the first time. This check is made by comparing the current depth to the length of the list containing right view nodes. If the depth is greater than the length of the list, it means you’re visiting this level for the first time. The node’s value is then added to this list. After processing a node, you traverse its right subtree before its left subtree. This ensures that nodes in the right subtree are processed first and are more likely to be the first nodes encountered at their respective depths. When you return to the same level (i.e., when traversing the left subtree of a node), the depth remains the same for nodes at that level. The depth doesn’t change because it’s passed as an argument to the recursive calls. However, since the right subtree is processed first, nodes at this level are already captured in the list if this depth was previously encountered.

To implement above algorithm:

We will write a main function that first checks 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: