Print right view of a binary tree

Given a binary tree, print the values of nodes which would be present in right view of binary tree. A node will be in the right-view if it is the right-most node at its level (imagine level order traversal). For example,    

                1
          2             3
      4      5       6  
        8              9
          10

In the above tree,
node 1 is right-most node for level 0.
node 3 is right-most node for level 1.
node 6 is right-most node for level 2.
node 9 is right-most node for level 3.
node 10 is right-most node for level 4.
              
And therefore right view for this tree is 1,3,6,9,10


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

If we do a level order traversal of tree such that the right-most node of each level is visited before all other nodes in that level then all we need to do is to print out the first visited node at each level to print the right view of tree. This can be done by doing a level order traversal from right end to left end instead of usual traversal from left end to right end and keeping track of max-level seen so far to find out when the new level starts. As soon as we find out that the new level has started, we print out the current node that is being visited.

The steps for this algorithm are -
1. Initialize maxLevelSeenSoFar to -1 and call printRightViewLevelOrder(currentNode = root)
2. In function printRightViewLevelOrder if currentNode is null, do nothing and return.
3. Else, add tuple (node = currentNode, level = 0) to 'queue'.
4. while 'queue' is not empty do
       - remove the first tuple(currentNode, level) from the queue.
       - if (level > maxLevelSeenSoFar) then we know that we are starting to traverse a new level and this is the first(and right most) node for this new  level and therefore we print currentNode's value and update maxLevelSeenSoFar to level.
       - if right child of currentNode is not null then we add tuple (currentNode.right, level + 1) to 'queue'.
       - if left child of currentNode is not null then we add tuple (currentNode.left, level + 1) to 'queue'.    
       * Please note that we are adding right child of node to the 'queue' before left child to make sure that the right-most node in any level is visited before other nodes in that level.  

After execution of step #4, right view of tree would be printed.

Notice that this algorithm takes O(n) extra space. With the following algorithm, we can save on extra space.

This algorithm basically uses modified pre-order traversal. In this modified pre-order traversal we make sure that -
a. The right-most node of any given level is visited before other nodes in that level. This can be easily achieved by visiting right sub-tree of node before left sub-tree. Basically, in this traversal, we visit the node first, then visit the right sub-tree and finally the left sub-tree(N-R-L).
b. We print out the node value as soon as we encounter a node in the level that is greater than the maximum level seen so far and update maximum level seen so far to current level.

The steps of this algorithm are as following -
1. Initialize maxLevelSeenSoFar to -1 and call printRightView(currentNode = root, level = 0)
2. In function printRightView(currentNode, level),
    a. If currentNode is null, then we do nothing and return.
    b. Else, if (level > maxLevelSeenSoFar) we print out the currentNode's value and update maxLevelSeenSoFar to level.
    c. Make a recursive call printRightView(currentNode.right, level + 1) to make sure nodes in right sub-tree are visited.
    d. Make a recursive call printRightView(currentNode.left, level + 1) to make sure nodes in left sub-tree are visited.    
    ** Notice that while visiting nodes with recursive calls, printRightView(currentNode.right, level + 1) is called before printLeftView(currentNode.left, level + 1) in order to make sure that for any node, right sub-tree of that node is visited before left sub-tree. This guarantees that for any level, the right-most node is visited before other nodes in that level.

After execution of step #2, right view of tree would be printed.
      
Please checkout code snippet and algorithm visualization section for more details of the algorithm.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.LinkedList;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a binary tree, print the values of nodes which would be present in right of view of binary tree. 
 * A node will be in the right-view if it is the rightmost node at its level. 
 * @author Nilesh
 */

public class RightViewOfBinaryTree {

    class QueueNode
    {
        TreeNode node;
        int level;
        
        QueueNode(TreeNode node, int level)
        {
            this.node = node;
            this.level = level;
        }
    }
    
    class TreeNode
    {
        TreeNode left;
        TreeNode right;
        int val;
    
        public TreeNode(int x)
        {
            this.val = x;
        }
    }
    
    TreeNode root;

    
    /*
                            1
                      2             3
                  4      5       6  
                    8              9
                      10
    */

    private TreeNode createTree()
    {
        this.root = new TreeNode(1);
        TreeNode n1   = new TreeNode(2);
        TreeNode n2   = new TreeNode(3);
        TreeNode n3   = new TreeNode(4);
        TreeNode n4   = new TreeNode(5);
        TreeNode n5   = new TreeNode(6);
        TreeNode n6   = new TreeNode(8);
        TreeNode n7   = new TreeNode(9);
        TreeNode n8   = new TreeNode(10);
        
        root.left  = n1;
        root.right = n2;
        
        n1.left  = n3;
        n1.right = n4;
        
        n2.left  = n5;
        
        n3.right = n6;
        
        n5.right = n7;
        
        n6.right = n8;
        
        return root;
    }


    int maxLevelSoFar = -1;
    
    private void printRightViewLevelOrder(TreeNode currentNode)
    {
        if (currentNode == null) return;
        
        LinkedList<QueueNode> queue = new LinkedList();
        
        queue.add(new QueueNode(currentNode, 0));
        
        while (!queue.isEmpty())
        {
            QueueNode queueEntry = queue.remove();
            if (queueEntry.level > maxLevelSoFar)
            {
                maxLevelSoFar = queueEntry.level;
                System.out.println(queueEntry.node.val);
            }
            if (queueEntry.node.right != null)
                queue.add(new QueueNode(queueEntry.node.right, queueEntry.level + 1));

            if (queueEntry.node.left != null)
                queue.add(new QueueNode(queueEntry.node.left, queueEntry.level + 1));

        }
        
    }
    
    private void printRightView(TreeNode currentNode, int currentLevel)
    {
        if (currentNode == null) return;
        
        if (currentLevel > maxLevelSoFar)
        {
            System.out.println(currentNode.val);
            maxLevelSoFar = currentLevel;
        }
        
        printRightView(currentNode.right, currentLevel + 1);
        printRightView(currentNode.left, currentLevel + 1);
    }

    public static void main(String[] args)
    {
        RightViewOfBinaryTree tree = new RightViewOfBinaryTree();
        
        tree.createTree();
        
        tree.printRightView(tree.root, 0);
        
        // tree.printRightViewLevelOrder(tree.root);
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer