Step 1: Grasping the Problem

This problem is a pure binary tree problem. You are given a binary tree with integer value in each node. Suppose that you are on the right side of the tree, so you need to print the values of the nodes from top to bottom which you will see.

1
2
3
4
5
6
7

       5   <------- 👁
     /   \      
   3      7  <----- 👁
 /  \    / \    
4   1   1   12  <-- 👁

result = [5, 7, 12]

A very misleading approach to solve this problem is thinking of always going to the right child and print them out. This is completely wrong and the problem requires you to visit all nodes to solve. See some examples below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

       Tree 1

         5   <------- 👁
       /   \      
     3      7  <----- 👁
    /              
   4  <-------------- 👁
  /
 9  <---------------- 👁

result = [5, 7, 4, 9]


       Tree 2

         5   <------- 👁
       /   \      
     3      7  <----- 👁
    / \            
   4   6   <--------- 👁
  /   /
 9   2   <----------- 👁

result = [5, 7, 6, 2]

For visiting all the nodes in the tree, we need a tree traversal algorithm. We are at the right side of the tree and we need to print from top to bottom. That means we must do two things while traversing the tree.

1. We must visit the parent before visiting it’s children. Because we need to print from top to bottom. This gives us an intuition of using a pre-order traversal.
2. We must visit the right child of two siblings at the same level. Because we need to see the rightmost node first. This gives us an intuition of traversing the right child first in the pre-order traversal.

So we have came up with a pre-order traversal visiting the right child first. But how are we going to make sure that the node is shadowed by another node at the name level (and at it’s right side)? To do this, we can use a level variable and check if any node has already been visited at that height. If visited, we will continue traversing the nodes children without using itself for the answer. But a more elegant solution is taking parts of the left that is after our stored node. It will be cleared more in the implementation step.

Step 2: Recursing pre-order traversal

A recursive pre-order traversal can be thought dividing into subproblems and solving them recursively. First we see if the current node is None of not. If current node is None, we will return an empty result List.

1
2

if not root:
  return []

This also gives up guarantee for accessing the nodes children. Now that we can are sure that current node is not None, we go to our right child (Remember, we must visit the right child first) and do this same thing. “Doing the same thing for another node” is similar to calling the same function (recursively) with different parameters.

1

right = self.rightSideView(root.right)

Finally we do the same thing for the left child.

1

left = self.rightSideView(root.left)

Step 3: Creating Visited Nodes List

At this point, the recursive calls have finished and we will have the final result from both the right and left children. We just need to aggregate both results into one final list.

Let us see the example again in the below tree.

           5(1)
          /   \      
        3(3)   7(2)
        / \
    (6)4   6(4)
      /   /
  (7)9   2(5)

This is the breakdown of each recursive call and the list we want to return from those calls.

It is clear the every time we are returning the root itself first. And after that, we are also returning the result of right calls. So clearly for these two, the code will be something like this:

1

return [root.val] + right + # and the rest

We are wrapping the root.val so that python can concatenate the list for us. You could also do [root.val, *right] if you want, the result is the same.

Finally, we need to add the rest nodes (coming from the left subtrees). We can clearly tell that it will be a suffix of the left child’s recursive call’s return list. We know that if we have found n children from the right recursive call, we do not need the first n children from the left call (because they are shadowed by the right nodes). So we can remove first len(right) nodes from the left list and concatenate that with our result.

1

return [root.val] + right + left[len(right):]

This is it. The complete program just loops through the nodes recursively and at the end concatenates creating the list. The concatenation of python lists takes amortized O(1) time. So the complete time complexity is O(n) where there are n nodes in the tree. The space complexity is also O(n) in both average and worst case. The program is very small in python and given below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def rightSideView(self, root: TreeNode) -> [int]:
        if not root:
            return []
        right = self.rightSideView(root.right)
        left = self.rightSideView(root.left)
        return [root.val] + right + left[len(right):]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr)
            return {};
        vector<int> right = rightSideView(root->right);
        vector<int> left = rightSideView(root->left);
        vector<int> result;
        result.push_back(root->val);
        result.insert(result.end(), right.begin(), right.end());
        for(int level = right.size(); level < left.size(); level++)
            result.push_back(left[level]);
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null)
            return new ArrayList<Integer>();
        List<Integer> right = rightSideView(root.right);
        List<Integer> left = rightSideView(root.left);
        List<Integer> result = new ArrayList<Integer>();
        result.add(root.val);
        result.addAll(right);
        for(int level = right.size(); level < left.size(); level++)
            result.add(left.get(level));
        return result;
    }
}