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:

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:

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:

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:

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:

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:

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:

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: