Print Right View of A Binary Tree

Q: How do you print the right view of a Binary Tree?

a.) Perform a level order traversal on the tree in an iterative manner. b.) Modify the level order traversal to maintain nodes at the present level. c.) If the current node is the last node of the present level. d.) Print it.

Introduction

The right view of a binary tree presents the nodes visible to an observer positioned on the right side of the tree. These nodes consist of the rightmost nodes at each level, providing a clear perspective of the tree's structure from that vantage point. We will work on two different approaches to solve this problem.

Also see, Binary Search Tree

What is Right View of Binary Tree?

Since the idea of binary is one that we are all already familiar with. Let's now examine the binary tree's right view. The set of nodes that are visible to someone standing to the right of any given binary tree is known as the right view. The nodes at each level that are furthest to the right are those that the observer can see. Any other nodes which lie to the left of the leftmost nodes will be hidden here.

Example of Right View of a Binary Tree

Let’s understand using an example what would be the right view of a binary tree.

Example of the right side of a binary tree

In the above example, the line of sight is in the right direction. The right view of the tree wants the Ninja to observe all the nodes through the right and, in the above example, those visible nodes are - 10, 50, 100, 80, and 90. These nodes block the view of the rest of the nodes when the tree is viewed from the right direction, thus giving us only the rightmost nodes of the tree.

The problem statement is, Given any binary tree print the right view of the binary tree.

We can have two approaches to solve this problem. Let’s understand the concept a bit more before considering the algorithms.

The above figure shows that the last node in each level of the tree is the right view of the binary tree.

So instead of traversing the tree from left to right, we traverse each level from right to left.

Let’s have a look at the tree,

We can, therefore, say that the first node in this type of traversal is the right view of a binary tree. We have the first node of each level as follows -

Right traversal of the tree:-

Level 0 (root node) - 10

Level 1 - 50

Level 2 - 100

Level 3 - 80

Level 4 - 90

To obtain the above result, we have two types of traversals that can be used to solve the problem of the right view of a binary tree.

Recursive Traversal : can recursively print the right view
Iterative (Level Order) Traversal : the right view can be printed by simple iterations

Recommended: Try the Right View Problem yourself before moving on to the solution.

Recursive Approach

We will be solving the problem using reverse preorder traversal. The general preorder traversal means it follows the below structure -

But we would reverse the structure because eventually, we only need the first rightmost nodes,

Therefore, we will convert the above structure to,

The algorithm would use a concept of recursion as the node would pass for all right children and left children according to the level of the tree.

Algorithm for Recursive Approach

For this approach to find the right view of a binary tree, we will declare a variable level that we would set to 0. We will print all the nodes which are first to be visited when a new level is encountered in the tree.

We will reverse the general preorder traversal and call the right and then call the left child recursively and update the level whenever the function is called. This approach requires the reversal preorder traversal and the recursion concept to obtain the final result. Let’s go through the algorithm to understand the approach.


//set level = 0
//set maxlevel = 0
level = 0
function RightView(node,level)
{
    if(node == null) return
    //used to check if the level is traversed 
    //or is being visited for the first time
    if(level == list.size)
    {
      Print the value of the node
       Set maxlevel = level
    }
    
    RightView(node->right, level+1)
    RightView(node->left, level+1)
}

Input


            10
      /           \
   20              50
 /   \            /    \
30    40        60      100
               /   \
             70    80
                  /
                90

Java
C++
Python

Java

import java.util.*;
 
public class Main {
 
    public static class Node {
        int data = 0;
        Node left = null;
        Node right = null;
 
        Node(int data) {
            this.data = data;
        }
    }
 
    static int idx = 0;
    static int max_level = 0;
    public static Node create_Tree(int[] arr) {
        if (idx == arr.length || arr[idx] == -1) {
            idx++;
            return null;
        }
 
        Node node = new Node(arr[idx++]);
 
        node.left = create_Tree(arr);
        node.right = create_Tree(arr);
 
        return node;
    }
 
    public static void RightView (Node node, int level) {
        if (node == null) 
            return; 

        if (max_level < level) { 
            System.out.print(node.data + " "); 
            max_level = level; 
        } 
        RightView(node.right, level + 1); 
        RightView(node.left, level + 1);  
    }
 
    public static void viewSet(Node root) {
        RightView(root,1);
    }
 
    public static void solve() {
        int[] arr = {10,20,30,-1,-1,40,-1,-1,50,60,70,-1,-1,80,90,-1,-1,-1,100,-1,-1 };
        System.out.println("Using Recursion Method");
        Node root = create_Tree(arr);
        viewSet(root);
    }
 
    public static void main(String[] args) {
        solve();
    }
}

You can also try this code with Online Java Compiler

Run Code

C++

#include <iostream>
#include <vector>

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int data) {
        this->data = data;
        left = right = nullptr;
    }
};

int idx = 0;
int max_level = 0;

Node* create_Tree(const std::vector<int>& arr) {
    if (idx == arr.size() || arr[idx] == -1) {
        idx++;
        return nullptr;
    }

    Node* node = new Node(arr[idx++]);
    node->left = create_Tree(arr);
    node->right = create_Tree(arr);

    return node;
}

void right_view(Node* node, int level) {
    if (!node)
        return;

    if (max_level < level) {
        std::cout << node->data << " ";
        max_level = level;
    }
    right_view(node->right, level + 1);
    right_view(node->left, level + 1);
}

void view_set(Node* root) {
    right_view(root, 1);
}

int main() {
    std::vector<int> arr = {10, 20, 30, -1, -1, 40, -1, -1, 50, 60, 70, -1, -1, 80, 90, -1, -1, -1, 100, -1, -1};
    std::cout << "Using Recursion Method" << std::endl;
    Node* root = create_Tree(arr);
    view_set(root);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python

class TreeNode:
    def _init_(self, data):
        self.data = data
        self.left = None
        self.right = None

tree_index = 0
maximum_depth = 0

def build_tree(tree_data):
    global tree_index
    if tree_index == len(tree_data) or tree_data[tree_index] == -1:
        tree_index += 1
        return None

    node = TreeNode(tree_data[tree_index])
    tree_index += 1
    node.left = build_tree(tree_data)
    node.right = build_tree(tree_data)

    return node

def display_right_view(node, current_depth):
    global maximum_depth
    if not node:
        return

    if maximum_depth < current_depth:
        print(node.data, end=" ")
        maximum_depth = current_depth

    display_right_view(node.right, current_depth + 1)
    display_right_view(node.left, current_depth + 1)

def show_view(root):
    display_right_view(root, 1)

if _name_ == "_main_":
    tree_data = [10, 20, 30, -1, -1, 40, -1, -1, 50, 60, 70, -1, -1, 80, 90, -1, -1, -1, 100, -1, -1]
    print("Using Recursion Method")
    root = build_tree(tree_data)
    show_view(root)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity: The Time Complexity of the above approach to find the right view of a binary tree is O(N), where N is the number of nodes in the binary tree.

Space Complexity: The Space Complexity of the above approach to find the right view of a binary tree is O(H), where H is the height of the binary tree. In the case of skewed trees, the height of the tree can become N which gives a worst of O(N).

Must Read Recursion in Data Structure

Iterative Approach

We will solve the problem using the classic level order traversal and the queue data structure.

So, to perform Level Order Traversal, the nodes would be considered level-wise. This means that each node would access the child at each level before moving to the next level.

We have these nodes respective to each level,

Level 0 - 10

Level 1 - 20, 50

Level 2 - 30, 40, 60, 100

Level 3 - 70, 80

Level 4 - 90

Notice the last node in each level is the node that is to be printed for the result.

Algorithm for Iterative Approach

In the algorithm, we would do a level order traversal of the tree and would print the last node of each level. Since we will iterate using a for loop for each node in the level this approach is known as an Iterative Approach. We will use a queue as a data structure to store the last nodes for each level. We will be using the poll function of the queue to find the last element of the level. We will check the element’s position if it’s the previous element using the size of the queue. Now let us go through the algorithm for an iterative approach that is used to display the right view of a binary tree.

enqueue root
while queue is not empty
{
    // find the length of the queue
    int size = queue.size()
    // run a loop from 0 to size 
    for(i =0, i<size, i++)
    {
        dequeue root
        //check if the element is present at last
        if(i==size-1)
        {
            print node.data
        }
        enqueue left child
        enqueue right child
    }
}

Input


            10
      /           \
   20              50
 /   \            /    \
30    40        60      100
               /   \
             70    80
                  /
                90

Java
C++
Python

Java


import java.util.*;

public class Main {

    public static class Node {
        int data = 0;
        Node left = null;
        Node right = null;

        Node(int data) {
            this.data = data;
        }
    }

    static int idx = 0;

    public static Node create_Tree(int[] arr) {
        if (idx == arr.length || arr[idx] == -1) {
            idx++;
            return null;
        }

        Node node = new Node(arr[idx++]);

        node.left = create_Tree(arr);
        node.right = create_Tree(arr);

        return node;
    }

    public static void RightView(Node node) {
        Queue<Node> que = new LinkedList<>();
        que.add(node);

        while (que.size() != 0) {

            int size = que.size();
            for(int i =0;i<size;i++) {
                Node n = que.poll();

                if(i== size-1) {
                    System.out.print(n.data + " ");
                }
                if(n.left !=null) {
                    que.add(n.left);
                }
                if(n.right != null) {
                    que.add(n.right);
                }
            }
        }
    }


    public static void solve() {
        int [] arr ={10,20,30,-1,-1,40,-1,-1,50,60,70,-1,-1,80,90,-1,-1,-1,100,-1,-1 };
        Node root = create_Tree(arr);
        System.out.println("Using Iterative Approach");
        RightView(root);
    }

    public static void main(String[] args) {
        solve();
    }
}

You can also try this code with Online Java Compiler

Run Code

C++


#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;

  TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

int currentIndex = 0;

TreeNode *BuildTree(vector<int> &nums) {
  if (currentIndex == nums.size() || nums[currentIndex] == -1) {
    currentIndex++;
    return nullptr;
  }

  TreeNode *node = new TreeNode(nums[currentIndex++]);
  node->left = BuildTree(nums);
  node->right = BuildTree(nums);

  return node;
}

void PrintRightView(TreeNode *root) {
  queue<TreeNode *> nodeQueue;
  nodeQueue.push(root);

  while (!nodeQueue.empty()) {
    int size = nodeQueue.size();
    for (int i = 0; i < size; i++) {
      TreeNode *currentNode = nodeQueue.front();
      nodeQueue.pop();

      if (i == size - 1) {
        cout << currentNode->val << " ";
      }
      if (currentNode->left != nullptr) {
        nodeQueue.push(currentNode->left);
      }
      if (currentNode->right != nullptr) {
        nodeQueue.push(currentNode->right);
      }
    }
  }
}

int main() {
  vector<int> nums = {10, 20, 30, -1, -1, 40, -1, -1, 50, 60, 70, -1, -1, 80, 90, -1, -1, -1, 100, -1, -1};
  TreeNode *root = BuildTree(nums);
  cout << "Using Iterative Approach" << endl;
  PrintRightView(root);
  return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Python



from collections import deque

class TreeNode:
    def _init_(self, data):
        self.data = data
        self.left = None
        self.right = None

def build_tree(tree_data):
    if not tree_data:
        return None
    node_list = [TreeNode(val) if val != -1 else None for val in tree_data]
    for i, node in enumerate(node_list):
        if node:
            if 2*i + 1 < len(node_list):
                node.left = node_list[2*i + 1]
            if 2*i + 2 < len(node_list):
                node.right = node_list[2*i + 2]
    return node_list[0]

def display_right_view(root):
    if not root:
        return
    queue = deque([(root, 0)])
    depth = -1
    while queue:
        node, node_depth = queue.popleft()
        if node_depth > depth:
            print(node.data, end=" ")
            depth = node_depth
        if node.right:
            queue.append((node.right, node_depth + 1))
        if node.left:
            queue.append((node.left, node_depth + 1))

if _name_ == "_main_":
    tree_data = [10, 20, 30, -1, -1, 40, -1, -1, 50, 60, 70, -1, -1, 80, 90, -1, -1, -1, 100, -1, -1]
    print("Using Iterative Method")
    root = build_tree(tree_data)
    display_right_view(root)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity: The Time complexity of the Iterative Approach to find the right view of a binary tree is O(N), where N is the number of nodes in the tree.

Space Complexity: The Space Complexity of the Iterative Approach to find the right view of a binary tree is O(N), where N is the number of nodes in the tree.

Frequently Asked Questions

Which approach is better for finding the right view of a binary tree?

The recursive approach is better than the iterative approach as a limited O(H) space is used in the algorithm, where H is the tree’s height. Whereas the Iterative algorithm uses level order traversal, the worst case in a level order traversal is much more than the recursive approach.

How do you print the right view of a Binary Tree?

Perform a level order traversal on the tree in an iterative manner.
Modify the level order traversal to maintain nodes at the present level.
If the current node is the last node of the present level.
Print it.

What is the left-to-right order of a binary tree?

The left-to-right order of a binary tree refers to the sequence in which nodes are traversed and processed, starting from the left child and moving to the right child of each parent node.

How is the view tree used?

In data structures, the view tree is a hierarchical representation of nodes in a tree-like structure, commonly used in graphical user interfaces (GUIs) to organize and visualize data relationships for efficient manipulation and display.

Conclusion

In this blog, we learned how to find the right view of a binary tree and how we can use different approaches to solve this problem. Printing the right view of a binary tree involves displaying the nodes that are visible when the tree is viewed from the right side. This view is achieved by traversing the tree level by level and recording the last node encountered at each level. Implementing this efficiently often requires a level-order traversal with additional tracking to ensure the rightmost nodes are captured. This approach provides a clear representation of the tree's structure from a rightward perspective, aiding in various applications and visualizations.

If you want to learn about finding the left view of a binary tree, we have a separate article that covers the approaches used to solve the problem. Do give it a read.
Recommended Reading:

Also, check out some of our blogs on Code360.