Print Right View of a Binary Tree

The right view of binary tree is the set of nodes seen by an observer as standing to the right of a given binary tree. The nodes visible to the observer will be the rightmost nodes at each level. All the other nodes (which will lie to the left of the rightmost nodes) will be hidden since they will lie behind the rightmost nodes in their respective levels.

Scope of Article

This article discusses

• Problem statement for the right view of the binary tree
• Approaches to print the right view of a given binary tree in data structures:
  • Recursive (or Depth-first Search) approach
  • Iterative (or Breadth-first search) approach
• Program implementation of the above-mentioned approaches in C++ and Python
• Complexity analysis of the algorithms used

Takeaways

Time and Space complexity:

• Time Complexity: O(n)
• Space Complexity : O(n)

Introduction

Imagine you’re a Star Wars character leading a bunch of Resistance spaceships to attack a First Order base called the Death Tree (similar to the Death Star).

You command your troopers to get in a linear formation and attack the base at once. The launched missiles hit the base on the right side at once as shown.

The set of nodes where the explosion is taking place makes up the right view of binary tree. Having gained a visual introduction, let us describe the right view of the binary tree in the upcoming section.

What is the Right View of Binary Tree?

The right view of binary tree is the part of the tree observed by an observer standing right to the tree and facing it.

Therefore, the right view consists of the rightmost nodes of each valid level of the tree.

But, what is a level?

We can define the level of a binary tree as the set of nodes that have an equal number of edges between themselves and the root node (that is, nodes equidistant from the root).

For example, consider the tree with root node as 1:

The nodes present in each level are given as:

Please note that you can start labelling the levels from either 0 or 1.

Example of Right View of Binary Tree

Consider again the tree we used above. As we said earlier, the rightmost node of each level will be part of our right view of the binary tree. That is:

Therefore, the right view of the binary tree is

1 3 4 8

Or, visually, the right view of the binary tree is as follows:

Taking another example, consider the tree shown below:

Therefore, the right view of the given binary tree is

1 3 4 6 7 8

Algorithm

There are two approaches to solve this problem, one is recursive (depth-first-search based) approach, while the other is iterative (breadth-first-search based) approach.

Recursive / DFS Approach

Intuition

1. DFS is one of the most basic traversal techniques for a graph/tree, therefore, we can try solving our problem using it.
2. Suppose I am in a given level, it appears that the algorithm should consider the right subtree with higher importance than the left one, since we have to print the rightmost node. This can be achieved by a right-oriented pre-order traversal, that is, current node, followed by right subtree, followed by the left subtree.
3. In any given level, the algorithm must ONLY print the rightmost node, and if it has been printed, the algorithm must not print any other node (in that level).
4. It can be achieved by using a variable which keeps track of the last level for which the rightmost node has been printed.
5. Now, if that variable’s value is less than the value of the given level, it means that we are in a level whose rightmost node has not been printed. Therefore, we must print whatever node we first encounter/process in this level.
6. Since our traversal is right oriented (see point 2), then we will always reach the rightmost node of a level before other nodes of that level.

Now, let’s see the algorithm where we used all the points we discussed above.

The Recursive Algorithm

1. Initialize two variables: a. curr_level: The current level of the tree we are currently present in during the traversal b. last_printed_level: The last level for which the rightmost node has been printed/stored.
2. Process the following sequentially in a recursive manner: a. Current node b. Right subtree c. Left subtree
3. At the current node (if it is not null) check whether the current level > last printed level. a. If Yes: Print / store the current node and update the value of last_printed_level to curr_level. b. If No: Continue
4. Before calling the function recursively on the right and left subtree, increase the value of level by 1.

Note:

The variable last_printed_level should either be a global variable (not recommended) or be passed by reference to function calls (recommended). This is done to ensure that the current level is compared to most recently updated value of last_printed_level.

Please see the animated gif below to for a better visual understanding of the algorithm.

Iterative / BFS Approach

Intuition

This, perhaps, is the most intuitive way of solving this problem.

1. We travel the entire tree level by level (from right to left).
2. At each level, we print/store the right most node.
3. After the algorithm is done processing the entire tree, we will obtain the right view of the binary tree given to us.

The Iterative Algorithm

1. Initialize a queue data structure ((commonly used in BFS algorithm) with the root node and a LevelEnd character to mark a level’s end in the queue. Commonly, nullptr or NULL is used as LevelEnd in C/C++, while None is used in Python.
2. While the queue is not empty, do the following: a. Pop the front of the queue, and call it frontVal b. If frontVal is LevelEnd, and the resultant queue is not empty, pop and print the front value of the resultant queue (this is the rightmost node of the given level), and also push a LevelEnd character into the queue. c. If frontVal is LevelEnd and the resultant queue is empty, break out of the while loop. d. If frontVal is not LevelEnd, then push its right child followed by left child into the queue (they must exist, of course).

Explanation

1. The above stated algorithm is just a right-oriented version of the standard Level-Order-Traversal algorithm.
2. Between any two LevelEnd characters, an entire level of the given tree is present (except, of course, the level 0, that is, the root node)
3. Since we give priority to the right child node over the left child node while pushing into the queue (see step 2.c of the algorithm) we ensure that the queue contains levels in a right to left fashion with respect to the binary tree given.
4. Because of the above point, we can be sure that the node just after the LevelEnd character in the queue is the rightmost node in the given binary tree’s level. Therefore, we printed it in step (2.b) of the algorithm.

Note:

Please note that it is not necessary to push the right child first. If we had pushed the left child of the current node into the queue, then in step (2.b) we would print the node just before the LevelEnd characters instead of other way round.

The reason for this is that the resultant queue will contain levels in left to right fashion with respect to the given binary tree.

See the animated gif given below for a better visual understanding of the algorithm.

Right View Of Binary Tree: Code Implementation

Before you see the code solution below, it is recommended that you try to implement the above-discussed algorithms yourself here on InterviewBit.

C++ (DFS Approach)

/*
Definition for a binary tree node.
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
};
*/


// utility function
void right_view_util(TreeNode* root, int &last_printed_level, int curr_level)
{
    // if root is null, there is nothing to do
    if(root==nullptr)
    {
        return;
    }

    if(last_printed_level<curr_level)
    {
        cout << root->val <<" ";
        last_printed_level = curr_level;
    }

    right_view_util(root->right, last_printed_level, curr_level+1);
    right_view_util(root->left, last_printed_level, curr_level+1);

    return;
}

void print_right_view(TreeNode* root)
{
    int curr_level = 1;
    int last_printed_level = 0;

    // print the right view
    right_view_util(root, last_printed_level, curr_level);

    return;
}

Explanation

• As explained in the algorithm, the code traverses the given tree in the fashion (current node-> right subtree->left subtree).
• At each node, if the last_printed_level<curr_level, we print the current level.
• To keep the value of the variable last_printed_level up-to-date, we pass it by reference to each recursive call.

Python (DFS Approach)

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

def right_view_util(root, last_printed_level, curr_level):

    if(root==None):
        return

    # if current level has not been printed
    if(last_printed_level[0]<curr_level):
        print(root.val)
        last_printed_level[0] = curr_level

    right_view_util(root.right, last_printed_level, curr_level+1)
    right_view_util(root.left, last_printed_level, curr_level+1)

    return

def print_right_view(root):

    curr_level = 1
    last_printed_level = [0]

    # print the right view
    right_view_util(root, last_printed_level, curr_level)

    return

C++ (BFS Approach)

/*
Definition for a binary tree node.
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
};
*/

void print_right_view(TreeNode* root)
{
    if(root==nullptr)
    {
        return;
    }

    // declaring an empty queue for Level Order Traversal
    queue<TreeNode*> Q;

    // the first level of the tree
    Q.push(root);
    Q.push(nullptr);

    // printing the root
    cout << root->val << " ";

    // processing the rest of the tree
    while(!Q.empty())
    {
        TreeNode* front = Q.front();

        // if front is nullptr
        // it means that current level has ended
        if(front==nullptr)
        {
            Q.pop();
            if(!Q.empty())
            {
                // print the value of the front node
                cout << Q.front()->val <<" ";
                Q.push(nullptr);
            }

            continue;
        }


        // since this node is not the rightmost node
        // remove it from the queue
        Q.pop();


        // add the next nodes to the queue
        // with right node having higher priority
        if(front->right!=nullptr)
        {
            Q.push(front->right);
        }
        if(front->left!=nullptr)
        {
            Q.push(front->left);
        }

    }

    return;
}

Explanation

• A queue is initialized which can store node pointer values.
• We perform a right-oriented level-order traversal. Therefore, after popping out a LevelEnd character, the next value in queue is the rightmost node of the level we are currently processing in the queue. So, we print it and pop it from the queue.
• Rest all the nodes are not printed.

Python (BFS Approach)

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

def print_right_view(root):
        if not root: 
            return

        # declaring a queue
        node_queue = collections.deque()
        node_queue.append(root)
        node_queue.append(None)

        # print the root
        print(root.val, end = ' ')

        # process the rest of the tree
        while node_queue:
            front_node=node_queue.popleft()

            if front_node==None:
                if not node_queue:
                    break
                else:
                    print(node_queue[0].val, end=' ')
                    node_queue.append(None)
                    continue

            if front_node.right:
                node_queue.append(front_node.right)

            if front_node.left:
                node_queue.append(front_node.left)

Complexity Analysis

1. Time Complexity: Since all the nodes are processed exactly once, therefore if the number of nodes present in the tree is of order $n$, then the time complexity of both the algorithms we used to find the right view of the binary tree is:

$$
\mathcal{O}(n)
$$

2. Space Complexity:
   a. DFS Solution : $\mathcal{O}(h)$, where $h$ is the height of the binary tree
   b. BFS Solution : $\mathcal{O}(n)$, where $n$ is the order of number of nodes in the binary tree

Conclusion

1. Right view of binary tree consists of the rightmost nodes of each level in the binary tree.
2. Two methods can be used to obtain the right view of binary tree; one uses a DFS approach, and the other uses a BFS approach.
3. While using the DFS (recursive) approach, we keep track of the level we are currently in, and the last level for which we have already obtained the rightmost node.
4. While using the BFS (iterative) approach, we perform a level order traversal and store/print the rightmost node in any given level.