Left View of Binary Tree

by · January 21, 2021

“Left View of Binary Tree” is a very popular interview problem based on Tree data structure, asked in many technical interviews. Here, we are given a binary tree and our task is to write a program to print the Left View of Binary Tree.

Left View of Binary Tree
Left View of Binary Tree

“Left View of Binary Tree” is defined as the nodes of the binary tree which are visible from left sides of the tree. These nodes are basically first nodes of every level of given binary tree.

There can be multiple ways to print left view of binary tree. Some of them are:

  1. Modifying Preorder Traversal
  2. Modifying Level Order Traversal

Method 1: Modifying Preorder Traversal

Here, the idea is to traverse given tree in preorder manner and maintain maximum level visited so far.

If current level is more than maximum level visited so far, then current node is first node of current level, then we print the current node and also update the maximum level visited so far to current level.

We perform all this operation in recursive manner.

C++ Program to Print Left View of Binary Tree is as follows:

/* C++ Program to Print Left View of Binary Tree */
#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to Print Left View of Binary Tree */
void leftViewPrint(Node *root, int curr_level, int &max_level)
{
    /* Base Case */
    if(root == NULL)
    return;
    
    /* 
        If current level is greater than maximum level visited so far,
        then, print the current node and update the maximum level visited 
        so far to current level
    */
    if(curr_level > max_level)
    {
        cout<<root -> data<<" ";
        max_level = curr_level;
    }
    
    /* Recursively Traverse for Left and Right Subtree */
    leftViewPrint(root -> left, curr_level+1, max_level);
    leftViewPrint(root -> right, curr_level+1, max_level);
}

/* Function to Print Left View of binary Tree */
void leftView(Node *root)
{
    int max_level = 0;
    
    leftViewPrint(root, 1, max_level);
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to print left view of binary tree */
    cout<<"The Left View of Binary Tree is:\n";
    leftView(root);
}

OUTPUT:

The Left View of Binary Tree is:
1 2 4 8

METHOD 2: Modifying Level Order Traversal

This is a simple modification of Level Order Traversal. Here, the idea is to print only first visited node of every level. This can be easily achieved by tracking the number of nodes at current level and first node of current level.

C++ Program to Print Left View of Binary Tree is as follows:

/* C++ Program to Print Left View of Binary Tree */
#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;


/* Function to Print Left View of binary Tree */
void leftView(Node *root)
{
    /* Base Case */
    if(root == NULL)
    return;
    
    queue<Node*> que;
    que.push(root);
    
    while(!que.empty())
    {
        /* Keeping Track of number of nodes at current level */
        int p = que.size();
        
        for(int i = 1; i <= p; i++)
        {
            Node *temp = que.front();
            
            /* If current node is first node of current level, print it */
            if(i == 1)
            {
                cout<<temp->data<<" "; 
            }
            
            /* Push Left and right Nodes*/
            if(temp -> left)
            que.push(temp -> left);
            if(temp -> right)
            que.push(temp -> right);
            
            /* Pop out current node */
            que.pop();
        }
        
    }
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to print left view of binary tree */
    cout<<"The Left View of Binary Tree is:\n";
    leftView(root);
}

OUTPUT:

The Left View of Binary Tree is:
1 2 4 8

Related Posts:

  1. Right View of Binary Tree
  2. Compute Height of Binary Tree
  3. Inorder Tree Traversal Using Stack
  4. Preorder Tree Trasversal Using Stack
  5. Postorder Tree Traversal Using Stack
  6. Vertical Order Tree Traversal
  7. Top View of Binary Tree
  8. Bottom View of Binary Tree
  9. Delete Complete Binary Tree
  10. Check if two trees are mirror Trees of Each Other
  11. Convert Binary Tree to its Mirror Tree
  12. Check if Binary Tree is Symmetric or Not
  13. Print All Root to Leaf Paths in a Binary Tree
  14. Introduction to Tree Data Structure
  15. Binary Tree Traversals
  16. Print All Leaf Nodes of a Binary Tree
  17. Count Number of Nodes in a Binary Tree
  18. Print Alternate Levels of Binary Tree
  19. Maximum Width of Binary Tree
  20. Level Order Tree Traversal

You may also like...