Given a Binary Tree, you need to print the Left view and right view of a Binary Tree. Level Order input for the Binary Tree is given.

1. Left View

sample input: 1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 -1
sample output: 1 2 4

The tree looks like:

             1
          /      \
       2           3
    /     \           \
   4       5           6

The root node constitutes level 0, nodes 2 and 3 represents level 1 and so on. The level keeps increasing as we traverse down the tree from the root node.

Left view of a tree indicates the nodes which are visible when the tree is viewed from the left side. We can clearly observe the nodes 1, 2 and 4 are visible from left hand side.

The most basic institution lies in realizing the fact that the number of elements in the output list is equal to the number of levels present in the Binary Tree.

Since we have 3 levels, hence we have 3 elements in the output solution. This establishes the fact that the left most node at each new level would be a part of the solution.

void leftView(node *root, int level, int &max_level) {
    if(root == NULL)
        return;

    if(level > max_level) {
        // we have encountered the left most element in the new level
        cout << root->data << " ";
        max_level = level;
    }

    // recursive calls: NLR preorder traversal
    leftView(root->left, level + 1, max_level);
    leftView(root->right, level + 1, max_level);
}

We perform a preorder traversal of the Binary Tree (NLR) starting from the root node. Initially the value of level would be 0 and that of max_level would be -1. Whenever we encounter a new level via the preorder traversal, we simply print that left most node.

In the recursive calls we will increase the level by 1 as the children of a particular node lies in the next level. This statement if(level > max_level) allows us to print the left most node, disregarding all other nodes in the same level since max_level keeps increasing by 1 unit.

2. Right View

sample input: 1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 -1
sample output: 1 3 6

The tree looks like:

             1
          /      \
       2           3
    /     \           \
   4       5           6

As you might have already discovered, this problem is exactly the same as the previous one. Instead of printing the left most element, we need to print the right most element. For this we just need to change the order of traversal. Here we would be following NRL traversal so that the righmost nodes are traversed first.

Following is the full code implementation in C++.

#include <iostream>
#include <queue>
using namespace std;

class node {
    public:
        int data;
        node *left;
        node *right;

        node(int data) {
            this->data = data;
            left = right = NULL;
        }
};

node* buildTreeLevelWise() {
    int data;
    cin >> data;

    node *root = new node(data);
    queue<node*> q;
    q.push(root);

    while(!q.empty()) {
        node *temp = q.front();
        q.pop();
        int child1, child2;
        cin >> child1 >> child2;

        if(child1 != -1) {
            temp->left = new node(child1);
            q.push(temp->left);
        }
        if(child2 != -1) {
            temp->right = new node(child2);
            q.push(temp->right);
        }
    }
    return root;
}

void rightView(node *root, int level, int &max_level) {
    if(root == NULL)
        return;
    if(level > max_level) {
        cout << root->data << " ";
        max_level = level;
    }
    // NRL traversal
    rightView(root->right, level + 1, max_level);
    rightView(root->left, level + 1, max_level);
}

int main() {
    int max_level = -1;
    node *root = buildTreeLevelWise();
    rightView(root, 0, max_level);

    return 0;
}