Left view of a binary tree

You are given a binary tree, you need to print the left view of it.

Consider the tree in the below figure.

The left view of the tree would be {8, 3, 1, 4}.

Algorithm

  1. Create a queue which would store the nodes of the tree. Insert the root node in the tree.
  2. While the queue is not empty, we do the following.
    Compute the size of the queue at each iteration. You need to print the first node of each level in the tree. At each iteration, loop for i = 1 to n.
    If i=1, it means that it is the first node of the level. Print the node and insert the left and right child to the queue and pop the current node. For all other nodes in the current level, push the left and right child of the current node and pop the node from the queue.

Check out the complete code in C++.

#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void leftView(Node* root){
    queue<Node*> q;
    q.push(root);
    while(!q.empty()){
        int n = q.size();
        for(int i = 1; i <= n; i++){
            Node* temp = q.front();
            q.pop();
            if(i==1){
                cout<<temp->data<<" ";
            }
            if(temp->left){
                q.push(temp->left);
            }
            if(temp->right){
                q.push(temp->right);
            }
        }
    }
}


void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    cout<<"Level order traversal: ";
    levelOrderTraversal();
    cout<<endl<<"Left view: ";
    leftView(root);
    return 0;
}

Also, check out another popular interview problem Construct a binary tree from preorder and postorder traversals.

One comment

Leave a Reply

Your email address will not be published.