title: Print bottom view of a binary tree
body: <p>For a binary tree we define horizontal distance as follows:</p>
  
  <pre><code>    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.
  </code></pre>
  
  <p>The bottom view of a tree then consists of all the nodes of the tree, where there is no node with the same <code>hd</code> and a greater level. (There may be multiple such nodes for a given value of <code>hd</code>. 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.</p>
  
  <hr>
  
  <p>Examples:</p>
  
  <p>Suppose the binary tree is:</p>
  
  <pre><code>         1
          /  \
         2    3
        / \  / \
       4   5 6  7
              \
               8
  </code></pre>
  
  <p>Bottom view of the tree is: 4 2 5 6 8 7</p>
  
  <pre><code>    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
  </code></pre>
  
  <p>One more example for reference :</p>
  
  <pre><code>         1
        /     \
      2         3
     / \       / \
    4   5     6     7 
   / \ / \   / \    / \
  8  9 10 11 12 13 14 15     
  </code></pre>
  
  <p>So the output for this will be :
  8 4 9 10 12 5 6 11 13 14 7 15</p>
  
  <pre><code>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
  </code></pre>
  
  <hr>
  
  <p>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:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;cstdio&gt;
  #include &lt;map&gt;
  #include &lt;vector&gt;
  
  using namespace std;
  
  struct Node{
         int data;
         struct Node *left, *right;
  };
  
  Node* newNode(int data)
  {
      Node *temp = new Node;
      temp-&gt;data = data;
      temp-&gt;left = temp-&gt;right = NULL;
      return temp;
  }
  
  int height(Node *node)
  {
      if(node == NULL)
              return 0;
      else{
           int lh = height(node-&gt;left);
           int rh = height(node-&gt;right);
  
           if(lh &gt; rh)
                 return (lh+1);
           else
                 return (rh+1);
      }
  }
  
  void printBottom(Node *node, int level, int hd, int min, map&lt; int, vector&lt;int&gt; &gt;&amp; 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-&gt;data);
                }
       }
       else if(level &gt; 1)
       {
            printBottom(node-&gt;left, level-1, hd-1, min, visited, lev, l);
            printBottom(node-&gt;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 &lt; *min)
            *min = hd;
       else if(hd &gt; *max)
            *max = hd;
  
       findMinMax(node-&gt;left, min, max, hd-1);
       findMinMax(node-&gt;right, min, max, hd+1);
  }
  
  int main()
  {
      Node *root = newNode(1);
      root-&gt;left = newNode(2);
      root-&gt;right = newNode(3);
      root-&gt;left-&gt;left = newNode(4);
      root-&gt;left-&gt;right = newNode(5);
      root-&gt;right-&gt;left = newNode(6);
      root-&gt;right-&gt;right = newNode(7);
      root-&gt;left-&gt;left-&gt;left = newNode(8);
      root-&gt;left-&gt;left-&gt;right = newNode(9);
      root-&gt;left-&gt;right-&gt;left = newNode(10);
      root-&gt;left-&gt;right-&gt;right = newNode(11);
      root-&gt;right-&gt;left-&gt;left = newNode(12);
      root-&gt;right-&gt;left-&gt;right = newNode(13);
      root-&gt;right-&gt;right-&gt;left = newNode(14);
      root-&gt;right-&gt;right-&gt;right = newNode(15);
  
      int min = 0, max = 0;
  
      findMinMax(root, &amp;min, &amp;max, 0);
  
      int lev[max-min+1];
      map &lt; int, vector&lt;int&gt; &gt; visited;
      map&lt; int,vector&lt;int&gt; &gt; :: iterator it;
  
      for(int i = 0; i &lt; max-min+1; i++)
              lev[i] = 0;
  
      int h = height(root);
  
      for (int i=h; i&gt;0; i--){
          printBottom(root, i, 0, min, visited, lev, i);
      }
  
      for(it = visited.begin() ; it != visited.end() ; it++) {
          for(int i=0 ; i &lt; it-&gt;second.size() ; i++) {
              cout &lt;&lt; it-&gt;second[i] &lt;&lt; " ";
          }
      }
  
      return 0;
  }
  </code></pre>
  
  <p>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?</p>