Right view of binary search tree

Right view of binary search tree

Given a binary search tree, print right view of binary search tree, i.e all the nodes which will be seen if binary tree is looked at from right hand side. For example, in below tree, right hand side view will be: 10,15,17. This problem is asked in different ways for example : if we switch on a torch on to the right side of binary tree, list down all the nodes on which light will fall directly on.

right view of binary search tree

What is seen when we look at tree from right hand side? What is the observation? It is that once we see a node from right side, we can not see any node which are on the same level behind this node. This current node obstructs all other nodes.

Idea here is very simple, all nodes which are at levels which are less than already visited level, will not be visible as they will be obstructed by one or more nodes on right hand side on already visited node. Since we need to visit the right most node first, take care that we need to start from right child here.

If the current node is at level which is greater than maximum level we have visited till now, that node will be visible. Let’s work out an example.

We start with level 0 at root. Let’s say, maximum level we have gone to till now is -1.

At node 30, current level (0) is greater than max level (-1), so node 30 will be visible from right hand side. Also update the max level to current level.

Now move to right side of current node, to node 40. Again current level (1) greater than max level (0), hence 40 is also visible. Update the max level as 1.
Same in case of node 45. Max level becomes 2 now.
Now move to left side of node 40, to node 37. Again current level (2) equal to max level (2), hence 37 is not visible.
Till now we have processed right sub tree of tree.Now move to left sub tree.
At node 20, current level is 1 and max level is 2, hence it not visible, obstructed by node 40.
At node 10, current level is 2 and max level is 2, hence it not visible, obstructed by node 45.
At node 12, current level becomes 3 and max level is 2, hence this node will be visible.
Implementation wise, it’s just a preorder processing, only right child is visited before left child. Keep track of maximum level we have seen so far and current level of the node.

Right view of binary search 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 currentLevel, int *maxLevel){
 
	if(!node) return;
 
	if(currentLevel >  *maxLevel){
		printf("%d  ", node->value);
		*maxLevel = currentLevel;
	}
	printRightView(node->right, currentLevel+1, maxLevel);
	printRightView(node->left, currentLevel+1, maxLevel);
}

/* driver program */
Node * createNode(int value){
	Node *newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
	return newNode;
}
 
Node *addNode(Node *node, int value){
	if(!node){
	     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;
}

As we will be visiting each node only once, complexity of to print right view of binary tree is O(N).

Please share if there is something is wrong or missing. If you are interested in contributing to website, please contact us.