Given a Binary Tree you need to print the top view and bottom view of the Binary Tree. Level order input for the Binary Tree is given.

1. Top view

sample input: 1 2 3 4 5 6 -1 -1 -1 -1 -1 -1 -1
sample output: 4 2 1 3
The tree looks like:

             1
          /      \
       2           3
    /     \       /
   4       5     6

When viewed from the top the nodes 1, 2, 4 and 3 are visible. This problem is similar to left view of a Binary Tree. You can observe that the extreme nodes at the horizontal distance from the root node are constituted in the solution output. Node 2 is at a distance of -1 from the root node and node 6 is at a distance +2. The first node at all possible distances from the root node constitutes the solution output. The main reason behind the usage of queue data structure so the top most node at a horizontal level is visited before any other node of the same horizontal distance below it.

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

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

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

node* buildLevelWiseTree() {
    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 topView(node *root) {
    if(root == NULL)
        return;

    map<int, int> m; // {distance, node->data}
    queue<pair<node*, int>> q; // {node, horizontal distance from the root node}
    q.push(make_pair(root, 0));

    while(!q.empty()) {
        node *front = q.front().first;
        int distance = q.front().second;
        q.pop();

        if(m.find(distance) == m.end())
            m.insert({distance, front->data});

        // insert the children if they exist
        if(front->left) 
            q.push(make_pair(front->left, distance - 1));
        if(front->right)
            q.push(make_pair(front->right, distance + 1));
    }

    // print the result
    for(auto p : m) 
        cout << p.second << " ";
}

int main() {

    node *root = buildLevelWiseTree();
    topView(root);

    return 0;
}

We make use of map STL class which stores the keys in sorted order. This map is used for storing the horizontal distance from the root node and its corresponding node value. We also maintain a queue of pair consisting of node pointer and the horizontal distance from the root node. Initially we push the root node in the queue. While the queue is not empty, we pop the first element and its corresponding horizontal distance from the root node. If this distance is not present in the map, we can update this distance in the map with the node data value. To facilitate the BFS traversal, we add the children of the current node in the queue if they exist. While pushing the left node in the tree, we would decrease the distance by 1 and we increment it by 1 for the right node.

So, our map stores the first encountered node for a horizontal distances from the root node.

2. Bottom view

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

The tree looks like:

             1
          /      \
       2           3
    /     \       /
   4       5     6

Note: Here 5 and 6 are at the same position, so we consider the right one to lower.

I hope the logic behind the algorithm for Top view of a Binary Tree is clear. The main idea was to store the first encountered node value at each level as it would block the remaining nodes at the same horizontal distance from the root node ie. all the nodes below it would not be visible when viewed from the top.

Opposite is the case for Bottom view. Here, we want the last encountered node at each level for all possible horizontal distances.

This could be simply achieved by updating the map for all the node values. Once, the while loop terminates, the map would have been updated by the last encountered nodes.

Below is the full implementation of the above logic.

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

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

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

node* buildLevelWiseTree() {
    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 bottomView(node *root) {
    if(root == NULL)
        return;

    map<int, int> m; // {distance, node->data}
    queue<pair<node*, int>> q; // {node, horizontal distance from root node}
    q.push(make_pair(root, 0));

    while(!q.empty()) {
        node *front = q.front().first;
        int distance = q.front().second;
        q.pop();

        m[distance] = front->data;
        // insert the children if they exist
        if(front->left) 
            q.push(make_pair(front->left, distance - 1));
        if(front->right)
            q.push(make_pair(front->right, distance + 1));
    }

    // print the result
    for(auto p : m) 
        cout << p.second << " ";
}

int main() {

    node *root = buildLevelWiseTree();
    bottomView(root);

    return 0;
}

The above approach could also be implemented by imposing a condition based on height and thereby performing a simple pre-order traversal. In such a case, queue data structure would not be needed.