Last Updated on December 14, 2022 by Prepbytes
Problem Statement:
The problem is straightforward: we have given a binary tree and we have to print the right view of the binary tree.
Let’s discuss it with an example:
Output: 10 30 15 14
These nodes are the rightmost nodes of their respective levels.
What is a Binary Tree?
Binary tree is a type of Tree data structure in which every node in the tree will have 2 or less than 2 child nodes and those child nodes will be termed as the left child and the right child of the node.
So, if we observe carefully, we’ll find that the right view of a binary tree is the last node encountered at every level.Therefore, we can use the queue data structure to traverse each level of the binary tree. At each level, we print only the value of the last node found at each level.
Algorithm:
- Push root into the queue.
- Traverse the queue until it gets empty.
- Find the length of the queue (q.size()).
- Run a loop from 0 to size of the queue.
- Pop the value of root.
- Check if the element is present at the end or not.
- If the condition is true then print that element.
- Else, push the left and right child of the queue.
Code Implementation:
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printRightView(Node* root)
{
if (!root)
return;
queue<Node*> q;
q.push(root);
while (!q.empty())
{
int n = q.size();
for(int i = 1; i <= n; i++)
{
Node* temp = q.front();
q.pop();
if (i == n)
cout<<temp->data<<" ";
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
}
}
int main()
{
Node* root = newNode(100);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(70);
root->left->right = newNode(80);
root->right->right = newNode(15);
root->right->left = newNode(12);
root->right->right->left = newNode(14);
printRightView(root);
}
import java.util.*;
class PrintRightView
{
private static class Node
{
int data;
Node left, right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
private static void printRightView(Node root)
{
if (root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty())
{
int n = queue.size();
for (int i = 1; i <= n; i++) {
Node temp = queue.poll();
if (i == n)
System.out.print(temp.data + " ");
if (temp.left != null)
queue.add(temp.left);
if (temp.right != null)
queue.add(temp.right);
}
}
}
public static void main(String[] args)
{
Node root = new Node(100);
root.left = new Node(20);
root.right = new Node(30);
root.left.left = new Node(70);
root.left.right = new Node(80);
root.right.right = new Node(15);
root.right.left = new Node(12);
root.right.right.left = new Node(14);
printRightView(root);
}
}
class newNode: def __init__(self, key): self.data = key self.left = None self.right = None self.hd = 0 def printRightView(root): if (not root): return q = [] q.append(root) while (len(q)): n = len(q) for i in range(1, n + 1): temp = q[0] q.pop(0) if (i == n) : print(temp.data, end = " " ) if (temp.left != None) : q.append(temp.left) if (temp.right != None) : q.append(temp.right) if __name__ == '__main__': root = newNode(100) root.left = newNode(20) root.right = newNode(30) root.left.left = newNode(70) root.left.right = newNode(80) root.right.right = newNode(15) root.right.left = newNode(12) root.right.right.left = newNode(14) printRightView(root)
This article tried to discuss Right View Binary Tree Using Queue. Hope this blog helps you understand the concept. To practice problems you can check out Foundation Course at PrepBytes.