Right view of a binary tree

Tags: , , ,

Right view of a binary tree

We learned different traversals of a binary tree like inorder, preorder, postorder, level order etc in previous posts. Today’s problem includes traversal of a binary tree too but in a different manner. The problem statement is to write a program to print the right view of a binary tree. The first question would be what is the right view of a binary tree?

Right view of a binary tree would be all the nodes of the binary tree which are visible when the tree is looked at from the right-hand side of the binary tree. For example, we would see nodes: 10, 15, and 19 when we look at the binary tree below from the right side as node 7 will be hidden by node 15 and node 8,9 and 18 will be hidden by node 19.

right view of a binary tree
Right view of a binary tree

Right view of a binary tree: thoughts

What do we see when we look at the tree from the right-hand side? What is the observation? It is that once we see a node, we can not see any node which is on the same level behind the visible node. The visible node obstructs all other nodes.
Which node will be the first one to be visible? It would be the rightmost node on that level. So we have to visit the right child of a node first before we visit the left child. If there was a right child of a node, the left child will not be visible. How can we make sure even the cousins of the rightmost node are not visible?

The idea is simple, we will do a preorder traversal of a binary tree with the right child visited first. Why? Because if we see the right child, the left child will not be visible as explained above.

To make sure none of the cousins are visible of a rightmost node are visible, we have to keep track of the levels. When we reach a node, we see if the level of the node is deeper than already seen maximum level? If yes, this node is the rightmost node (Why? because we are visited right child first) on that level and should be visible. Now, the maximum visited level is this new level, all the nodes which are this new level will not be visible.

Right view of a binary tree: example

Let’s take an example and see how this method works.

right view of a binary tree

We have current max level traversed as -1. At node(10), we visit the level 0 which is greater than the current maximum. So node(10) should be visible in the right view of the binary tree.

right view of binary search tree

At node(15), we are moving down a level, so the current level would be 1, whereas current max visited level is 0. node(15)will be visible from the right-hand side of the tree. The max level visited is 1.

right side view of binary tree

As we are doing preorder traversal, we will visit node(19) next, which is at level 2 which is greater than max level, so, node(19) will be visible in the right view of the binary tree.

right view of binary tree

Next, we visit the node(18), which is at the level 2, which is equal to max level, hence node(18) will not be visible.

node(7) is at the level 1, which is less than current max level 2, so it will not be visible. Same is the case for the node(8) and node(9).

Right view of a binary tree: implementation

#include<stdio.h>
#include<stdlib.h>

struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

void printRightView(Node * node, int currLevel, int *maxLevel){

	if(node == NULL) return;

	if(currLevel >  *maxLevel){
		printf("%d  ", node->value);
		*maxLevel = currLevel;
	}
	printRightView(node->right, currLevel+1, maxLevel);
	printRightView(node->left, currLevel+1, maxLevel);
}
/* driver program */
Node * createNode(int value){
	Node *temp =  (Node *)malloc(sizeof(Node));
	temp->value = value;
	temp->right= NULL;
	temp->left = NULL;
	return temp;
}

Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

int main(){

    Node *root = NULL;
    //Creating a binary tree
    root = addNode(root,6);
    root = addNode(root,3);
    root = addNode(root,2);
    root = addNode(root,1);
    root = addNode(root,7);
    root = addNode(root,5);
    root = addNode(root,9);
    
    int max = -1;
    printRightView(root, 0, &max);

    return 0;
}

We visit each node only once, complexity of above code is O(n).

Please share if there is something wrong or missing. If you are willing to contribute and share your learning with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com

Please signup for free interview material.