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

Complete Binary tree

In this article, we will discuss the complete binary tree. But before start discussing the complete binary tree, we should first see a brief description of a binary tree. What is...

7 minutes read.

Bin Packing Problem (How to minimize the number of used Bins)

You have been given an array. The values of the array represent the size of n different items. You have been also given some bins. You have to store the...

3 minutes read.

Primitive Data Structure in C

The data structure is a logical or mathematical model for organizing and structuring the main memory or elements. We can classify the data structures in two ways one is primitive, and...

10 minutes read.

Binary Tree to Doubly Linked List

Binary Tree to Doubly Linked List This article will explain how to convert the given binary tree into a Doubly Linked List. The left and right pointers in tree nodes are...

2 minutes read.

Stack vs Queue: Data Structure

 Difference Between Stack and Queue What is Stack? The LIFO principle applies on insertion and deletion operations of the stack which means last inserted element to the stack will remove first....

3 minutes read.

Lowest common ancestor in a binary search tree

Suppose you have given two values of nodes in a binary search tree. You have to find out the lowest common ancestor between the nodes. Let’s take an example tree- For the...

4 minutes read.

LCA of binary tree

Implementation //Writing a program to find the lowest common factor in a given binary search tree. #include <iostream> #include <vector> using namespace std; // the very first step is to create a binary tree. struct __nod { int...

8 minutes read.

Threaded Binary Trees

Introduction Threaded Binary Trees (TBTs) are an enhancement of normal binary trees intended for in-order traversal only. This means that this data structure is developed with the objective of making the...

12 minutes read.

Array vs Linked List: Data Structure

Data structure: Difference Between Array and Linked List What is Array? An array is a linear data structure that can store similar data items for further processing. The similar data items...

3 minutes read.

Equal Sum

Find an element in array such that the sum of left array is equal to the sum of right array You have been given an array of numbers. You have to...

4 minutes read.

Program to calculate the area of the circumcircle of an equilateral triangle

You have given one value which represents the side of the equilateral triangle. You have to find out the area of the circumcircle. Let’s take an example - For the above...

3 minutes read.

Linear vs Binary Search: Data Structure

Difference Between Linear and Binary Search What is Linear Search? A linear search also referred as a sequential search. It is a way to find an element within a list and it...

3 minutes read.

Operations on 2D-Arrays

Two Dimensional Array Operations Adding Elements to Two-D Arrays We must put data in both rows and columns when inserting items in 2-D Arrays. As a result, we employ the idea of...

10 minutes read.

Red Black Tree

Red Black Tree A red-black tree is referred as self-balancing binary search tree. The tree was invented by Rudolf Bayer in 1972. In red-black, each node stores an extra bit that...

8 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.

Circular Linked List

Circular Linked List A circular linked list where all nodes are connected to their next node and last node is connected to the starting node or we can say all nodes...

5 minutes read.

What is a Height-Balanced Tree in Data Structure

A height-balanced tree is a type of binary tree. If the absolute difference between the heights of the left and right subtree is less than or equal to 1, then...

6 minutes read.

Strings in Data Structures

Strings and functions in C A string is a collection of characters. We'll learn how to declare strings, operate with strings in C programming, and use pre-defined string handling routines. We'll look...

7 minutes read.

Time Complexity of Selection Sort in Data Structure

What is Time Complexity? The term “Time complexity” can be defined as the number of times executions made of a particular sequence of instructions and not the total amount of time...

3 minutes read.

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...

8 minutes read.