Print Left View of a Binary Tree

Problem: Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side.

For example: Given the following tree, the left view of tree is 5, 9, 14, 19

Method 1: The naive approach is to do level order traversal of the binary tree and print the first node of all the levels.

Method 2: We can also do this problem using recursion. The idea is to keep track of maximum level and the current level. Whenever current level is greater than the maximum level so far obtained, we print the current node because this is the first node in its level.

Below is the implementation of the idea.

#include <bits/stdc++.h>
using namespace std;
 
struct node
{
    int data;
    node *left;
    node *right;
};
 
/* utility function to create a new Binary Tree node */
node* newNode(int data)
{
    node *temp = new node();
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
/* function to print the left view of the binary tree */
void leftView(node *root, int *max_level, int cur_level)
{
    /* base case */
    if(root == NULL)
        return;
 
    /* if the current node is first node in level */
    if(*max_level < cur_level)
    {
        cout<<root->data<<" ";
        *max_level = cur_level;
    }
 
    /* recursive call for left and right sub tree */
    leftView(root->left, max_level, cur_level + 1);
    leftView(root->right, max_level, cur_level + 1);
}
 
/* driver function */
int main()
{
    node *root                = newNode(5);
    root->left                = newNode(9);
    root->right               = newNode(27);
    root->left->left          = newNode(14);
    root->right->right        = newNode(11);
    root->right->right->left  = newNode(19);
    root->right->right->right = newNode(21);
 
    int max_level = 0;
    leftView(root, &max_level, 1);
    cout<<"\n";
 
    return 0;
}

Output:

5 9 14 19

Time Complexity: O(n)