Print bottom view of a binary tree
First, you can get the time complexity down to ${\cal O}(n)$, while keeping the same space complexity. You can do this by filling visited in a single run of printBottom:

void printBottom(Node *node, int level, int hd, int min, map&lt; int, vector&lt;int&gt; &gt;&amp; visited, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] &lt; level){
         lev[hd-min] = level;
         visited[hd-min] = new vector&lt;int&gt;; //erase old values, they are hidden by the current node
     }
     if(lev[hd-min] &lt;= level){
         visited[hd-min].push_back(node-&gt;data);
     }
     printBottom(node-&gt;left, level+1, hd-1, min, visited, lev);
     printBottom(node-&gt;right, level+1, hd+1, min, visited, lev);
}


with the initial call printBottom(root, 1, 0, min, visited, lev);

If you insist on the nodes beig output in order of increasing value of hd, I don't think you can improve space consumption. However, if you allow a different order of output, you can get rid of visited, by first determining for each value of 'hd', which level should be output and then making another pass, printing the values that match:

void fillLev(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] &lt; level){
         lev[hd-min] = level;
     }
     fillLev(node-&gt;left, level+1, hd-1, min, lev);
     fillLev(node-&gt;right, level+1, hd+1, min, lev);
}
void printBottom(Node *node, int level, int hd, int min, int lev[])
{
     if(node == NULL)
             return;
     if(lev[hd-min] == level){
         cout &lt;&lt; node-&gt;data;
     }
     printBottom(node-&gt;left, level+1, hd-1, min, lev);
     printBottom(node-&gt;right, level+1, hd+1, min, lev);
}


with calls fillLev(root, 1, 0, min, lev); and printBottom(root, 1, 0, min, lev);.