Left and Right View of a Binary Tree

By | October 27, 2015

Left View of a Binary Tree. Right View of a Binary Tree.

Given a binary tree, we need to print how the tree will look when viewed from left side and right side.

Left and Right View of a Binary Tree Example:

             80                 
           /     \        
          60      110     
         /  \    /       
       35   40  85   
      /  \
     64   72

For the tree shown above, the output should be
Left View:    80 60 35 64
Right View:  80 110 85 72

Left and Right View of a Binary Tree Solution:

Method 1:

We use a variable to store the maximum level whose node is printed. Compare it with the level of the present node, if the level of the present node is greater than the value of thevariable we print the data of the node.

Algorithm:

  1. Send level of each node as a parameter to the function.
  2. Keep a MaxLevel variable, that stores the maximum level whose 1 node has been printed.
    This variable is passed as a parameter to the function. We initialise it to -1 so that level 0 node is also printed.
  3. if the node is NULL, we do nothing.
  4. If the level of the present node is greater than the value of MaxLevel , we update the value of MaxLevel and print the data of the present node.
  5. For Left View, we Recur first on the Left subtree then on the right subtree, with level+1.
  6. For Right View, we Recur first on the Right subtree then on the left subtree with level+1.

Left and Right View of a Binary Tree Solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure for each node of the tree*/
struct node
{
   int data;
   node *right,*left;
};


/*Function that allocates memory for
each new node and initialises it*/
node * newNode(int data)
{
   node *temp=new node;
   temp->data=data;
   temp->left=NULL;
   temp->right=NULL;
   
   return temp;
}

/*In the following two functions,we print the node
if and only if its level is greater than the MaxLevel
i.e. it is the left most node of new level for Left View,
and right most node of new level for Right View.

For left view, we Recur on left Subtree first and
for right View we recur on Right Subtree first*/


/*This function prints the Left View of the Binary Tree*/
void LeftView(node * root, int level, int &MaxLevel)
{
   if(!root)
      return ;
   /*Call by reference is used for MaxLevel*/	
   if( MaxLevel<level)	
   {
      cout<<root->data<<" ";
      MaxLevel=level;
   }
   /*Recur on left subtree first,then right
   NOTE that the level +1 is sent for next level*/
   LeftView(root->left,level+1,MaxLevel);
   LeftView(root->right,level+1,MaxLevel);
}

/*This function prints the right View of the Binary Tree*/
void RightView(node * root, int level, int &MaxLevel)
{
   if(!root)
      return ;
   /*Call by reference is used for MaxLevel*/	
   if( MaxLevel<level)	
   {
      cout<<root->data<<" ";
      MaxLevel=level;
   }
   /*Recur on right subtree first,then left,
   NOTE that the level +1 is sent for next level*/
   RightView(root->right,level+1,MaxLevel);
   RightView(root->left,level+1,MaxLevel);
   
}

int main()
{
  /*        
  We are making the following tree
  	          80                 
            /    \        
          60      110     
         /  \    /       
       35   40  85 
      /  \
     64  72
  This is a BST.
  */
  node *root               = newNode(80);
  root->left               = newNode(60);
  root->right              = newNode(110);
  root->left->left         = newNode(35);
  root->left->right        = newNode(40);   
  root->right->left 	   = newNode(85);  
  root->left->left->left   = newNode(64);
  root->left->left->right  = newNode(72);
  
  /*The value of MaxLevel is taken as 
  -1 so that the root node is printed*/
  int MaxLevel=-1; 
  cout<<"The left View of Binary tree is:\n";
  LeftView(root,0,MaxLevel);
  
  MaxLevel=-1; //reseting
  cout<<"\nThe left View of Binary tree is:\n";
  RightView(root,0,MaxLevel);
  
  return 0;
}

Output:

The left View of Binary tree is:
80 60 35 64 
The left View of Binary tree is:
80 110 85 72

Time Complexity: O(N)  where N is the number of nodes in the tree.
All the nodes are visited here.