Given a Binary Tree, print the Right view of it.
The right view of a Binary Tree is a set of nodes visible when the tree is visited from the Right side.
Examples:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
Output: Right view of the tree is 1 3 7 8Input:
1
/
8
/
7
Output: Right view of the tree is 1 8 7
Right View of a Binary Tree using Recursion:
The idea is to use recursion and keep track of the maximum level also. And traverse the tree in a manner that the right subtree is visited before the left subtree.
Follow the steps below to solve the problem:
- Perform Postorder traversal to get the rightmost node first
- Maintain a variable name max_level which will store till which it prints the right view
- While traversing the tree in a postorder manner if the current level is greater than max_level then print the current node and update max_level by the current level
Below is the implementation of the above approach:
C++
// C++ program to print right view of Binary Tree#include <bits/stdc++.h>using namespace std;struct Node { int data; struct Node *left, *right;};// A utility function to// create a new Binary Tree Nodestruct Node* newNode(int item){ struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->data = item; temp->left = temp->right = NULL; return temp;}// Recursive function to print// right view of a binary tree.void rightViewUtil(struct Node* root, int level, int* max_level){ // Base Case if (root == NULL) return; // If this is the last Node of its level if (*max_level < level) { cout << root->data << "\t"; *max_level = level; } // Recur for right subtree first, // then left subtree rightViewUtil(root->right, level + 1, max_level); rightViewUtil(root->left, level + 1, max_level);}// A wrapper over rightViewUtil()void rightView(struct Node* root){ int max_level = 0; rightViewUtil(root, 1, &max_level);}// Driver Codeint main(){ struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->right->right->right = newNode(8); rightView(root); return 0;}// This code is contributed by SHUBHAMSINGH10 |
C
// C program to print right view of Binary Tree#include <stdio.h>#include <stdlib.h>struct Node { int data; struct Node *left, *right;};// A utility function to create a new Binary Tree Nodestruct Node* newNode(int item){ struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->data = item; temp->left = temp->right = NULL; return temp;}// Recursive function to print right view of a binary tree.void rightViewUtil(struct Node* root, int level, int* max_level){ // Base Case if (root == NULL) return; // If this is the last Node of its level if (*max_level < level) { printf("%d\t", root->data); *max_level = level; } // Recur for right subtree first, then left subtree rightViewUtil(root->right, level + 1, max_level); rightViewUtil(root->left, level + 1, max_level);}// A wrapper over rightViewUtil()void rightView(struct Node* root){ int max_level = 0; rightViewUtil(root, 1, &max_level);}// Driver Program to test above functionsint main(){ struct Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); rightView(root); return 0;} |
Java
// Java program to print right view of binary tree// A binary tree nodeclass Node { int data; Node left, right; Node(int item) { data = item; left = right = null; }}// class to access maximum level by referenceclass Max_level { int max_level;}class BinaryTree { Node root; Max_level max = new Max_level(); // Recursive function to print right view of a binary // tree. void rightViewUtil(Node node, int level, Max_level max_level) { // Base Case if (node == null) return; // If this is the last Node of its level if (max_level.max_level < level) { System.out.print(node.data + " "); max_level.max_level = level; } // Recur for right subtree first, then left subtree rightViewUtil(node.right, level + 1, max_level); rightViewUtil(node.left, level + 1, max_level); } void rightView() { rightView(root); } // A wrapper over rightViewUtil() void rightView(Node node) { rightViewUtil(node, 1, max); } // Driver program to test the above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.right.left.right = new Node(8); tree.rightView(); }}// This code has been contributed by Mayank Jaiswal |
Python
# Python program to print right view of Binary Tree# A binary tree nodeclass Node: # A constructor to create a new Binary tree Node def __init__(self, item): self.data = item self.left = None self.right = None# Recursive function to print right view of Binary Tree# used max_level as reference list ..only max_level[0]# is helpful to usdef rightViewUtil(root, level, max_level): # Base Case if root is None: return # If this is the last node of its level if (max_level[0] < level): print "%d " % (root.data), max_level[0] = level # Recur for right subtree first, then left subtree rightViewUtil(root.right, level+1, max_level) rightViewUtil(root.left, level+1, max_level)def rightView(root): max_level = [0] rightViewUtil(root, 1, max_level)# Driver program to test above functionroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.left = Node(6)root.right.right = Node(7)root.right.left.right = Node(8)rightView(root)# This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System;// C# program to print right view of binary tree// A binary tree nodepublic class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}// class to access maximum level by referencepublic class Max_level { public int max_level;}public class BinaryTree { public Node root; public Max_level max = new Max_level(); // Recursive function to print right view of a binary // tree. public virtual void rightViewUtil(Node node, int level, Max_level max_level) { // Base Case if (node == null) { return; } // If this is the last Node of its level if (max_level.max_level < level) { Console.Write(node.data + " "); max_level.max_level = level; } // Recur for right subtree first, then left subtree rightViewUtil(node.right, level + 1, max_level); rightViewUtil(node.left, level + 1, max_level); } public virtual void rightView() { rightView(root); } // A wrapper over rightViewUtil() public virtual void rightView(Node node) { rightViewUtil(node, 1, max); } // Driver program to test the above functions public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.right.left.right = new Node(8); tree.rightView(); }}// This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript program to print // right view of binary tree class Node { constructor(item) { this.left = null; this.right = null; this.data = item; } } let max_level = 0; let root; // Recursive function to print right view of a binary tree. function rightViewUtil(node, level) { // Base Case if (node == null) return; // If this is the last Node of its level if (max_level < level) { document.write(node.data + " "); max_level = level; } // Recur for right subtree first, then left subtree rightViewUtil(node.right, level + 1); rightViewUtil(node.left, level + 1); } function rightView() { rightview(root); } // A wrapper over rightViewUtil() function rightview(node) { rightViewUtil(node, 1); } root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.right.left.right = new Node(8); rightView();</script> |
Output
1 3 7 8
Right view of Binary Tree using Queue
Time Complexity: O(N), Traversing the Tree having N nodes
Auxiliary Space: O(N), Function Call stack space in the worst case.
Right View of a Binary Tree using Level Order Traversal:
The idea is to use Level Order Traversal as the last node every level gives the right view of the binary tree.
Follow the steps below to solve the problem:
- Perform level order traversal on the tree
- At every level print the last node of that level
Below is the implementation of above approach:
C++
// C++ program to print left view of// Binary Tree#include <bits/stdc++.h>using namespace std;// A Binary Tree Nodestruct Node { int data; struct Node *left, *right;};// Utility function to create a new tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp;}// function to print Right view of// binary treevoid printRightView(Node* root){ if (root == NULL) return; queue<Node*> q; q.push(root); while (!q.empty()) { // get number of nodes for each level int n = q.size(); // traverse all the nodes of the current level while (n--) { Node* x = q.front(); q.pop(); // print the last node of each level if (n == 0) { cout << x->data << " "; } // if left child is not null push it into the // queue if (x->left) q.push(x->left); // if right child is not null push it into the // queue if (x->right) q.push(x->right); } }}// Driver codeint main(){ // Let's construct the tree as // shown in example Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); printRightView(root);}// This code is contributed by// Snehasish Dhar |
Java
// JAVA program to print right view of// Binary Treeimport java.io.*;import java.util.LinkedList;import java.util.Queue;// A Binary Tree Nodeclass Node { int data; Node left, right; public Node(int d) { data = d; left = right = null; }}class BinaryTree { Node root; // function to print Right view of // binary tree void rightView(Node root) { if (root == null) { return; } Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { // get number of nodes for each level int n = q.size(); // traverse all the nodes of the current level for (int i = 0; i < n; i++) { Node curr = q.peek(); q.remove(); // print the last node of each level if (i == n - 1) { System.out.print(curr.data); System.out.print(" "); } // if left child is not null add it into // the // queue if (curr.left != null) { q.add(curr.left); } // if right child is not null add it into // the // queue if (curr.right != null) { q.add(curr.right); } } } } // Driver code public static void main(String[] args) { // Let's construct the tree as // shown in example BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.right.left.right = new Node(8); tree.rightView(tree.root); }}// This code is contributed by Biswajit Rajak |
Python3
# Python3 program to print right# view of Binary Treefrom collections import deque# A binary tree nodeclass Node: # A constructor to create a new # Binary tree Node def __init__(self, val): self.data = val self.left = None self.right = None# Function to print Right view of# binary treedef rightView(root): if root is None: return q = deque() q.append(root) while q: # Get number of nodes for each level n = len(q) # Traverse all the nodes of the # current level while n > 0: n -= 1 # Get the front node in the queue node = q.popleft() # Print the last node of each level if n == 0: print(node.data, end=" ") # If left child is not null push it # into the queue if node.left: q.append(node.left) # If right child is not null push # it into the queue if node.right: q.append(node.right)# Driver code# Let's construct the tree as# shown in exampleroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.left = Node(6)root.right.right = Node(7)root.right.left.right = Node(8)rightView(root)# This code is contributed by Pulkit Pansari |
C#
// C# program to print right view of// Binary Treeusing System;using System.Collections.Generic;// A Binary Tree Nodepublic class Node { public int data; public Node left, right; public Node(int d) { data = d; left = right = null; }}public class BinaryTree { public Node root; // function to print Right view of // binary tree public void rightView(Node root) { if (root == null) { return; } Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { // get number of nodes for each level int n = q.Count; // traverse all the nodes of the current level for (int i = 0; i < n; i++) { Node curr = q.Peek(); q.Dequeue(); // print the last node of each level if (i == n - 1) { Console.Write(curr.data); Console.Write(" "); } // if left child is not null add it into // the // queue if (curr.left != null) { q.Enqueue(curr.left); } // if right child is not null add it into // the // queue if (curr.right != null) { q.Enqueue(curr.right); } } } } // Driver Code public static void Main() { // Let's construct the tree as // shown in example BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.right.left.right = new Node(8); tree.rightView(tree.root); }}// This code is contributed by jana_sayantan. |
Javascript
<script> // JavaScript program to print left view of Binary Tree class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Utility function to create a new tree node function newNode(data) { let temp = new Node(data); return temp; } // function to print Right view of // binary tree function printRightView(root) { if (root == null) return; let q = []; q.push(root); while (q.length > 0) { // get number of nodes for each level let n = q.length; // traverse all the nodes of the current level while (n-- > 0) { let x = q[0]; q.shift(); // print the last node of each level if (n == 0) { document.write(x.data + " "); } // if left child is not null push it into the // queue if (x.left != null) q.push(x.left); // if right child is not null push it into the // queue if (x.right != null) q.push(x.right); } } } // Let's construct the tree as // shown in example let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printRightView(root); </script> |
Output
1 3 7 8
Time Complexity: O(N), where N is the number of nodes in the binary tree.
Auxiliary Space: O(N) since using auxiliary space for queue
Right View of a Binary Tree using Morris Traversal:
Follow the Steps to implement the approach:
- Initialize an empty vector res to hold the result.
- Initialize a pointer curr to the root of the binary tree.
- While curr is not null, do the following:
If curr has no right child:
Add the value of curr to res.
Set curr to its right child.
Otherwise:
Find the inorder successor of curr by initializing a pointer next to the right child of curr, and then repeatedly moving left until next has no left child or its left child is equal to curr.
If next has no left child:
Add the value of curr to res.
Set the left child of next to curr.
Set curr to its right child.
Otherwise:
Set the left child of next to null.
Set curr to its left child. - Return res, which contains the last node at each level of the binary tree as seen from the right side.
Below is the implementation of the above approach.
C++
// C++ code to implement the morris traversal approach#include <iostream>#include <vector>using namespace std;// Definition for a binary tree nodestruct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x) , left(NULL) , right(NULL) { }};vector<int> rightSideView(TreeNode* root){ vector<int> res; TreeNode* curr = root; while (curr) { if (!curr->right) { // if there is no right child , // add the current node's value // to the vector res.push_back(curr->val); curr = curr->right; // move to the right child } else { // if there is a right child TreeNode* next = curr->right; // set the next node to the // right child while (next->left && next->left != curr) { // traverse the left // subtree of the right // child untill a leaf // node or the current // node is reached next = next->left; } if (!next->left) { // if the left child of the // next node is NULL res.push_back(curr->val); next->left = curr; curr = curr->right; } else { next->left = NULL; curr = curr->left; } } } return res;}// Driver codeint main(){ TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->left = new TreeNode(6); root->right->right = new TreeNode(7); root->right->right->right = new TreeNode(8); vector<int> res = rightSideView(root); for (int i : res) { cout << i << " "; } cout << endl; return 0;}// This code is contributed by Veerendra_Singh_Rajpoot |
Java
import java.util.ArrayList;import java.util.List;// Definition for a binary tree nodeclass TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; this.left = null; this.right = null; }}public class RightSideView { public List<Integer> rightSideView(TreeNode root) { List<Integer> res = new ArrayList<>(); TreeNode curr = root; int n = 4; // You can set 'n' to any desired value while (curr != null) { if (curr.right == null) { // if there is no right child, // add the current node's value // to the list res.add(curr.val); curr = curr.left; // move to the left child } else { // if there is a right child TreeNode next = curr.right; // set the next node to // the right child while ( next.left != null && next.left != curr) { // traverse the left // subtree of the // right child until a // leaf node or the // current node is // reached next = next.left; } if (next.left == null) { // if the left child of the // next node is null res.add(curr.val); next.left = curr; curr = curr.right; } else { next.left = null; curr = curr.left; } } } return res.subList(0, Math.min(n, res.size())); } // Driver Code public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); root.right.right.right = new TreeNode(8); RightSideView rightSideView = new RightSideView(); List<Integer> res = rightSideView.rightSideView(root); System.out.println(res); }}// This code is contributed by Veerendra_Singh_Rajpoot |
Python3
# Python code to implement the morris traversal approach# Definition for a binary tree nodeclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef rightSideView(root): res = [] curr = root while curr: if not curr.right: # if there is no right child, # add the current node's value # to the vector res.append(curr.val) curr = curr.right # move to the right child else: # if there is a right child next = curr.right # set the next node to the # right child while next.left and next.left != curr: # traverse the left subtree of the right # child untill a leaf node or the current # node is reached next = next.left if not next.left: # if the left child of the # next node is NULL res.append(curr.val) next.left = curr curr = curr.right else: next.left = None curr = curr.left return res# Driver codeif __name__ == '__main__': root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7) root.right.right.right = TreeNode(8) res = rightSideView(root) for i in res: print(i, end=" ") print()# Contributed by adityasha4x71 |
C#
using System;using System.Collections.Generic;// Definition for a binary tree nodepublic class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; left = null; right = null; }}public class RightSideView{ public List<int> MorrisTraversal(TreeNode root) { List<int> res = new List<int>(); TreeNode curr = root; while (curr != null) { if (curr.right == null) { // If there is no right child, add the current node's value to the list res.Add(curr.val); curr = curr.right; // Move to the right child } else { // If there is a right child TreeNode next = curr.right; // Set the next node to the right child // Traverse the left subtree of the right child until a leaf node or the current node is reached while (next.left != null && next.left != curr) { next = next.left; } if (next.left == null) { // If the left child of the next node is null res.Add(curr.val); next.left = curr; curr = curr.right; } else { next.left = null; curr = curr.left; } } } return res; } // Driver code public static void Main(string[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.left = new TreeNode(6); root.right.right = new TreeNode(7); root.right.right.right = new TreeNode(8); RightSideView rightSideView = new RightSideView(); List<int> res = rightSideView.MorrisTraversal(root); foreach (int val in res) { Console.Write(val + " "); } Console.WriteLine(); }} |
Javascript
// Javascript code addition // Definition for a binary tree nodeclass TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}function rightSideView(root) { const res = []; let curr = root; let n = 4; while (curr) { if (!curr.right) { // if there is no right child , // add the current node's value // to the array res.push(curr.val); curr = curr.left; // move to the left child } else { // if there is a right child let next = curr.right; // set the next node to the // right child while (next.left && next.left !== curr) { // traverse the left // subtree of the right // child untill a leaf // node or the current // node is reached next = next.left; } if (!next.left) { // if the left child of the // next node is NULL res.push(curr.val); next.left = curr; curr = curr.right; } else { next.left = null; curr = curr.left; } } } return res.slice(0, n);}// Driver codeconst root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);root.right.right.right = new TreeNode(8);const res = rightSideView(root);console.log(res);// The code is contributed by Arushi Goel. |
Output
1 3 7 8
Time Complexity: O(n) , The time complexity of the Morris Traversal approach is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly twice (once when we find its inorder predecessor, and once when we visit it from its inorder predecessor).
Auxiliary Space: O(1) , The space complexity of the Morris Traversal approach is O(1), because we only use a constant amount of extra space for the res, curr, and next pointers. We do not use any additional data structures or recursive function calls that would increase the space complexity.
This article is contributed by Biswajit Rajak. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
