C++ – How to Print Bottom View of a Binary Tree?

For a binary tree we define horizontal distance as follows:

    Horizontal distance(hd) of root = 0
    If you go left then hd = hd(of its parent)-1, and 
    if you go right then hd = hd(of its parent)+1.

The bottom view of a tree then consists of all the nodes of the tree, where there is no node with the same hd and a greater level. (There may be multiple such nodes for a given value of hd. In this case all of them belong to the bottom view.) I'm looking for an algorithm that outputs the bottom view of a tree.

Examples:

Suppose the binary tree is:

         1
        /  \
       2    3
      / \  / \
     4   5 6  7
            \
             8

Bottom view of the tree is: 4 2 5 6 8 7

    Ok so for the first example,
    Horizontal distance of node with value 1: 0, level = 1
    Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
    Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
    Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
    Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
    Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
    Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
    Horizontal distance of node with value 8: 0 + 1 = 1, level = 4

    So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
    So for hd = -2, print 4
    for hd = -1, print 2
    for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
    for hd = 1, print 8
    for hd = 2, print 7

One more example for reference :

         1
      /     \
    2         3
   / \       / \
  4   5     6     7 
 / \ / \   / \    / \
8  9 10 11 12 13 14 15     

So the output for this will be :
8 4 9 10 12 5 6 11 13 14 7 15

Similarly for this example
hd of node with value 1: 0, , level = 1
hd of node with value 2: -1, level = 2
hd of node with value 3: 1, level = 2
hd of node with value 4: -2, level = 3
hd of node with value 5: 0, , level = 3
hd of node with value 6: 0, level = 3
hd of node with value 7: 2, level = 3
hd of node with value 8: -3, level = 4
hd of node with value 9: -1, level = 4
hd of node with value 10: -1, level = 4
hd of node with value 11: 1, level = 4
hd of node with value 12: -1, level = 4
hd of node with value 13: 1, level = 4
hd of node with value 14: 1, level = 4
hd of node with value 15: 3, level = 4

So, the output will be:
hd = -3, print 8
hd = -2, print 4
hd = -1, print 9 10 12
hd = 0, print 5 6
hd = 1, print 11 13 14
hd = 2, print 7
hd = 3, print 15 

So the ouput will be:
8 4 9 10 12 5 6 11 13 14 7 15

I already know a method in which I can do it using a lot of extra space (a map, and a 1-D array for storing the level of the last element in that vertical line) and with time complexity of $O(N \log N)$.
And this is the implementation of this method:

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>

using namespace std;

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

Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int height(Node *node)
{
    if(node == NULL)
            return 0;
    else{
         int lh = height(node->left);
         int rh = height(node->right);

         if(lh > rh)
               return (lh+1);
         else
               return (rh+1);
    }
}

void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
{
     if(node == NULL)
             return;
     if(level == 1){
              if(lev[hd-min] == 0 || lev[hd-min] == l){
                      lev[hd-min] = l;
                      visited[hd-min].push_back(node->data);
              }
     }
     else if(level > 1)
     {
          printBottom(node->left, level-1, hd-1, min, visited, lev, l);
          printBottom(node->right, level-1, hd+1, min, visited, lev, l);
     }
}

void findMinMax(Node *node, int *min, int *max, int hd)
{
     if(node == NULL)
             return;

     if(hd < *min)
          *min = hd;
     else if(hd > *max)
          *max = hd;

     findMinMax(node->left, min, max, hd-1);
     findMinMax(node->right, min, max, hd+1);
}

int main()
{
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(11);
    root->right->left->left = newNode(12);
    root->right->left->right = newNode(13);
    root->right->right->left = newNode(14);
    root->right->right->right = newNode(15);

    int min = 0, max = 0;

    findMinMax(root, &min, &max, 0);

    int lev[max-min+1];
    map < int, vector<int> > visited;
    map< int,vector<int> > :: iterator it;

    for(int i = 0; i < max-min+1; i++)
            lev[i] = 0;

    int h = height(root);

    for (int i=h; i>0; i--){
        printBottom(root, i, 0, min, visited, lev, i);
    }

    for(it = visited.begin() ; it != visited.end() ; it++) {
        for(int i=0 ; i < it->second.size() ; i++) {
            cout << it->second[i] << " ";
        }
    }

    return 0;
}

I am seeking help to do this in more optimized way, which used less space or time. Is there any other efficient method for this problem?