Logo
×

Right side view of binary tree

The right view of the binary tree is generally known to be that side viewed from the right direction of the point of view. To be more precise, the right-side view of the binary tree is one where an observer starts to see the binary tree from the Rt direction.

Implementation

// Writing a C++ program to print the Rt-side view of the given binary tree. 
#include <bits/stdc++.h>
using namespace std;


struct __Nod
{
	int record;
	struct __Nod *Lft, *Rt;
};


// creating a Utility function will help us build a new binary tree node. 
struct __Nod *nw__Nod(int itm)
{
	struct __Nod *temp = (struct __Nod *)malloc(
						sizeof(struct __Nod));
	temp->record = itm;
	temp->Lft = temp->Rt = NILL;
	return temp;
}


// Creating a recursive function that will help us print the right-side view of the binary tree. 
void RtViewUtil(struct __Nod *root,
				int level, int *mx_levl)
{
	if (root == NILL) return;


	// In case this has to be the last node of the level, then, 
	if (*mx_levl < level)
	{
		cout << root->record << "\t";
		*mx_levl = level;
	}


	// we have first to perform recursion for the right subtree. 
//We will have to do the same for the left subtree. 
	RtViewUtil(root->Rt, level + 1, mx_levl);
	RtViewUtil(root->Lft, level + 1, mx_levl);
}


// A wrapper will be placed over the right-view utility function.
void RtView(struct __Nod *root)
{
	int mx_levl = 0;
	RtViewUtil(root, 1, &mx_levl);
}


// writing the main code.
int main()
{
	struct __Nod *root = nw__Nod(1);
	root->Lft = nw__Nod(2);
	root->Rt = nw__Nod(3);
	root->Lft->Lft = nw__Nod(4);
	root->Lft->Rt = nw__Nod(5);
	root->Rt->Lft = nw__Nod(6);
	root->Rt->Rt = nw__Nod(7);
	root->Rt->Rt->Rt = nw__Nod(8);


	RtView(root);


	return 0;
}

Output:

Right side view of binary tree

Example 2)

#include <bits/stdc++.h>
using namespace std;
// creating a Utility function will help us build a new binary tree node. 
struct __Nod {
	int record;
	struct __Nod *Lft, *Rt;
};
// creating a Utility function will help us build a new binary tree node. 
__Nod* nw__Nod(int record)
{
	__Nod* temp = new __Nod;
	temp->record = record;
	temp->Lft = temp->Rt = NILL;
	return temp;
}


// Creating a recursive function that will help us print the right-side view of the binary tree. 
void printRtView(__Nod* root)
{
	if (root == NILL)
		return;


	queue<__Nod*> q;
	q.push(root);


	while (!q.empty()) {
		// we will now count the total number of nodes at each level.
		int n = q.size();


		// now, we will have to visit all the given nodes of the present level. 
		while (n--) {


			__Nod* x = q.front();
			q.pop();


			// now, we have to print the last node of each given level.
			if (n == 0) {
				cout << x->record << " ";
			}
			// first check, and if the left node or child is not empty, we have to push it into the queue. 
			if (x->Lft)
				q.push(x->Lft);
			// if the right node or child is not empty, we must push it into the queue. 
			if (x->Rt)
				q.push(x->Rt);
		}
	}
}


// writing the main code.
int main()
{
	__Nod* root = nw__Nod(1);
	root->Lft = nw__Nod(2);
	root->Rt = nw__Nod(3);
	root->Lft->Lft = nw__Nod(4);
	root->Lft->Rt = nw__Nod(5);
	root->Rt->Lft = nw__Nod(6);
	root->Rt->Rt = nw__Nod(7);
	root->Rt->Lft->Rt = nw__Nod(8);


	printRtView(root);
}

Output:

Right side view of binary tree

Example 3)

#include <iostream>
#include <list>
using namespace std;
 
// creating a structure to show where we can store the binary tree node.
struct __Nod
{
    int ky;
    __Nod *Lft, *Rt;
 
    __Nod(int ky)
    {
        this->ky = ky;
        this->Lft = this->Rt = NILLptr;
    }
};
 
//creating the iterative function will help us print the right-side view of the allotted binary tree.
void printRtView(__Nod* root)
{
    // we have to return the function if the tree is empty.
    if (root == NILLptr) {
        return;
    }
 
    // we have to create further and build an empty queue where we will be enrooting the root node. 
    list<__Nod*> queue;
    queue.push_back(root);
 
    // pointer to store the current __Nod
    __Nod* curr = NILLptr;
 
    // loop till queue is empty
    while (!queue.empty())
    {
        // calculate the total number of __Nods at the current level
        int size = queue.size();
        int i = 0;
 
        // process every __Nod of the current level and enqueue their
        // non-empty Rt and Rt child
        while (i++ < size)
        {
            curr = queue.front();
            queue.pop_front();
 
            // if this is the last __Nod of the current level, print it
            if (i == size) {
                cout << curr->ky << " ";
            }
 
            if (curr->Lft) {
                queue.push_back(curr->Lft);
            }
 
            if (curr->Rt) {
                queue.push_back(curr->Rt);
            }
        }
    }
}
 
int main()
{
    __Nod* root = new __Nod(1);
    root->Lft = new __Nod(2);
    root->Rt = new __Nod(3);
    root->Lft->Rt = new __Nod(4);
    root->Rt->Lft = new __Nod(5);
    root->Rt->Rt = new __Nod(6);
    root->Rt->Lft->Lft = new __Nod(7);
    root->Rt->Lft->Rt = new __Nod(8);
 
    printRtView(root);
 
    return 0;
}

Output:

Right side view of binary tree

Example 4)

#include <iostream>
#include <unordered_map>
using namespace std;
 
// Record structure to store a binary tree __Nod
struct __Nod
{
    int ky;
    __Nod *Lft, *Rt;
 
    __Nod(int ky)
    {
        this->ky = ky;
        this->Lft = this->Rt = NILLptr;
    }
};
 
// Traverse __Nods in reverse preorder fashion
void printRtView(__Nod* root, int level, auto &map)
{
    if (root == NILLptr) {
        return;
    }
 
    // insert the current __Nod and level information into the map
    map[level] = root->ky;
 
    // recur for the Left subtree before the Right subtree
    printRtView(root->Lft, level + 1, map);
    printRtView(root->Rt, level + 1, map);
}
 
// Function to print the Rt view of a given binary tree
int printRtView(__Nod* root)
{
    // create an empty map to store the last __Nod for each level
    unordered_map<int, int> map;
 
    // traverse the tree and fill in the map
    printRtView(root, 1, map);
 
    // iterate through the map and print the Rt view
    for (int i = 1; i <= map.size(); i++) {
        cout << map[i] << " ";
    }
}
 
int main()
{
    __Nod* root = new __Nod(1);
    root->Lft = new __Nod(2);
    root->Rt = new __Nod(3);
    root->Lft->Rt = new __Nod(4);
    root->Rt->Lft = new __Nod(5);
    root->Rt->Rt = new __Nod(6);
    root->Rt->Lft->Lft = new __Nod(7);
    root->Rt->Lft->Rt = new __Nod(8);
 
    printRtView(root);
 
    return 0;
}

Output:

Right side view of binary tree

Example 5)

#include <iostream>
using namespace std;
 
// Record structure to store a binary tree __Nod
struct __Nod
{
    int ky;
    __Nod *Lft, *Rt;
 
    __Nod(int ky)
    {
        this->ky = ky;
        this->Lft = this->Rt = NILLptr;
    }
};
 
// Recursive function to print the Rt view of a given binary tree
void printRtView(__Nod* root, int level, int &last_level)
{
    // base case: empty tree
    if (root == NILLptr) {
        return;
    }
 
    // if the current __Nod is the last __Nod of the current level
    if (last_level < level)
    {
        // print the __Nod's record
        cout << root->ky << " ";
 
        // update the last level to the current level
        last_level = level;
    }
 
    // recur for the Right and Left subtree by increasing the level by 1
    printRtView(root->Rt, level + 1, last_level);
    printRtView(root->Lft, level + 1, last_level);
}
 
// Function to print the Rt view of a given binary tree
void printRtView(__Nod* root)
{
    int last_level = 0;
    printRtView(root, 1, last_level);
}
 
int main()
{
    __Nod* root = new __Nod(1);
    root->Lft = new __Nod(2);
    root->Rt = new __Nod(3);
    root->Lft->Rt = new __Nod(4);
    root->Rt->Lft = new __Nod(5);
    root->Rt->Rt = new __Nod(6);
    root->Rt->Lft->Lft = new __Nod(7);
    root->Rt->Lft->Rt = new __Nod(8);
 
    printRtView(root);
 
    return 0;
}

Output:

Right side view of binary tree

Example 6)

// C program to print Rt view of Binary Tree
#include <stdio.h>
#include <stdlib.h>


struct __Nod {
	int record;
	struct __Nod *Lft, *Rt;
};


// A utility function to create a new Binary Tree __Nod
struct __Nod* nw__Nod(int itm)
{
	struct __Nod* temp
		= (struct __Nod*)malloc(sizeof(struct __Nod));
	temp->record = itm;
	temp->Lft = temp->Rt = NILL;
	return temp;
}


// Recursive function to print Rt view of a binary tree.
void RtViewUtil(struct __Nod* root, int level,
				int* mx_levl)
{
	// Base Case
	if (root == NILL)
		return;


	// If this is the last __Nod of its level
	if (*mx_levl < level) {
		printf("%d\t", root->record);
		*mx_levl = level;
	}


	// Recur for the Right subtree first, then the Left subtree
	RtViewUtil(root->Rt, level + 1, mx_levl);
	RtViewUtil(root->Lft, level + 1, mx_levl);
}


// A wrapper over RtViewUtil()
void RtView(struct __Nod* root)
{
	int mx_levl = 0;
	RtViewUtil(root, 1, &mx_levl);
}


// Driver Program to test the above functions
int main()
{
	struct __Nod* root = nw__Nod(1);
	root->Lft = nw__Nod(2);
	root->Rt = nw__Nod(3);
	root->Lft->Lft = nw__Nod(4);
	root->Lft->Rt = nw__Nod(5);
	root->Rt->Lft = nw__Nod(6);
	root->Rt->Rt = nw__Nod(7);
	root->Rt->Lft->Rt = nw__Nod(8);


	RtView(root);


	return 0;
}

Output:

Right side view of binary tree

Example 7)

# Python program to print Rt view of Binary Tree


# A binary tree __Nod




Class __Nod:
	# A constructor to create a new Binary tree __Nod
	def __init__(self, itm):
		self.record = itm
		self.Lft = None
		self.Rt = None


# Recursive function to print Rt view of Binary Tree
# used mx_levl as reference list ..only mx_levl[0]
# is helpful to us




def RtViewUtil(root, level, mx_levl):


	# Base Case
	If the root is None:
		return


	# If this is the last __Nod of its level
	if (mx_levl[0] < level):
		print "%d " % (root.record),
		mx_levl[0] = level


	# Recur for the Right subtree first, then the Left subtree
	RtViewUtil(root.Rt, level+1, mx_levl)
	RtViewUtil(root.Left, level+1, mx_levl)




def RtView(root):
	mx_levl = [0]
	RtViewUtil(root, 1, mx_levl)




# Driver program to test the above function
root = __Nod(1)
root.Lft = __Nod(2)
root.Rt = __Nod(3)
root.Lft.Lft = __Nod(4)
root.Lft.Rt = __Nod(5)
root.Rt.Lft = __Nod(6)
root.Rt.Rt = __Nod(7)
root.Rt.Lft.Rt = __Nod(8)


RtView(root)

Output:

Right side view of binary tree

Example 8)

// Java program to print Rt view of binary tree


// A binary tree __Nod
class __Nod {


	int record;
	__Nod Lft, Rt;


	__Nod(int itm)
	{
		record = itm;
		Lft = Rt = NILL;
	}
}


// class to access maximum level by reference
class Mx_levl {


	int mx_levl;
}


class BinaryTree {


	__Nod root;
	Mx_levl max = new Mx_levl();


	// Recursive function to print Rt view of a binary
	// tree.
	void RtViewUtil(__Nod __Nod, int level,
					Mx_levl mx_levl)
	{


		// Base Case
		if (__Nod == NILL)
			return;


		// If this is the last __Nod of its level
		if (mx_levl.mx_levl < level) {
			System.out.print(__Nod.record + " ");
			mx_levl.mx_levl = level;
		}


		// Recur for the Right subtree first, then the Left subtree
		RtViewUtil(__Nod.Rt, level + 1, mx_levl);
		RtViewUtil(__Nod.Lft, level + 1, mx_levl);
	}


	void RtView() { RtView(root); }


	// A wrapper over RtViewUtil()
	void RtView(__Nod __Nod)
	{


		RtViewUtil(__Nod, 1, max);
	}


	// Driver program to test the above functions
	public static void main(String args[])
	{
		BinaryTree tree = new BinaryTree();
		tree.root = new __Nod(1);
		tree.root.Lft = new __Nod(2);
		tree.root.Rt = new __Nod(3);
		tree.root.Lft.Lft = new __Nod(4);
		tree.root.Lft.Rt = new __Nod(5);
		tree.root.Rt.Lft = new __Nod(6);
		tree.root.Rt.Rt = new __Nod(7);
		tree.root.Rt.Lft.Rt = new __Nod(8);


		tree.RtView();
	}
}

Output:

Right side view of binary tree

Related Topics

2-3 Trees and Basic Operations on them

2-3 Trees, like any other AVL trees or B-trees, are just a type of Height Balanced Tree. 2-3 Trees are the B-trees of order 3. Like every other B-tree, the...

4 minutes read.

Finding the Maximum Element in a Binary Tree

Implementation // Creating a C++ program to excavate the minimum and maximum in a given binary tree. #include <bits/stdc++.h> #include <iostream> using namespace std; // creating a new tree node. class __nod { public: int record; __nod *Lft, *Rt; /*...

4 minutes read.

Remove duplicates from an unsorted Linked List

Remove duplicates from an unsorted Linked List This article will explain how we can remove duplicates from unsorted linked lists. Here we have given an unsorted singly linked list and will...

3 minutes read.

Introduction to Arrays

What exactly is an array? A group of related data pieces stored in contiguous memory regions is referred to as an array. It is the most basic data structure in which...

5 minutes read.

Counting Sort

Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the...

3 minutes read.

Shell Sort

Shell Sort: Shell sort is a sorting algorithm. It is an extended version of the insertion sort. In this sorting, we compare the elements that are distant apart rather than the...

5 minutes read.

Find all possible words from board

We have been given a dictionary of words and a board of characters from which we can form strings. Now, we have to check if the string is present in...

5 minutes read.

Adding one to the number represented an array of digits

You have given one array, which consists of values which represent the different digits of a number. You have to add 1 to this number and store the result in...

3 minutes read.

Common Operations on various Data Structures

Data structures are ways to organise data in computer memory for quick and effective use. The storage of data uses a variety of data-structures. It is also possible to define...

7 minutes read.

Priority Queue in Data Structure

Priority Queue A priority queue is a special kind of queue, in priority queue we give some priority to an element and according to this priority an element can be served...

3 minutes read.

Bitwise Operators and their Important Tricks

In most of the programs you write today, you deal with data types comprising bytes, such as integer, float, double, etc. Dealing with bytes? It is a quite normal task,...

5 minutes read.

How to get Better in Data Structures and Algorithms?

Introduction Data structures and algorithms are fundamental computer science concepts that store, organize, and process data efficiently. By understanding different data structures and algorithms and using them effectively, you can become...

19 minutes read.

Tree in Data Structure

Tree A tree is a non-linear data structure by which hierarchical data is displayed. As we know that there are many trees in the forest, similarly the data structure also contains...

3 minutes read.

Partitioning a linked list around a given value

Partitioning a linked list around a given value In this problem, we are given a linked list and a value k. We need to partition the given linked list so that...

3 minutes read.

Queue Data Structure

Queue in DS: The queue is a non-primitive and linear data structure. It works on the principle of FIFO (First In First Out). That is, the element that is added...

4 minutes read.

Semi-Structured data

In this article, we will discuss the semi-structured data. Data can be defined as the distinct piece of information that is gathered and translated for some purpose. It can be...

5 minutes read.

Hash Table vs STL Map

Hash table and STL map are extremely valuable information structures in software engineering. Here we will consider the examination between their properties to be well as execution.  To start with, we will...

7 minutes read.

Digital Search Tree in Data Structures

What is a digital search Tree in Data Structures? The Digital search tree is known for its application and diversity in the way it has impacted our world in the field...

3 minutes read.

Difference between Structured and Object-Oriented Analysis

Analysis means observing and collecting relevant information about the structure of something or the basic details of a system's requirements. Structured and Object Oriented Analysis are both widely used in...

2 minutes read.

Counts the number of times a given element occurs in a Linked List

Counts the number of times a given element occurs in a Linked List This article will explain how we can count the occurrences of a particular element in a list. Here,...

3 minutes read.