title: Print a Tree Vertically
body: <p>To understand what's same vertical line, we need to define horizontal distances first. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the below tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.</p>
  
  <p>Examples:</p>
  
  <pre><code>      1
      /   \
  
     2     3
  
    / \   / \
    4  5  6  7
  </code></pre>
  
  <p>The tree has 5 vertical lines</p>
  
  <p>Vertical-Line-1 has only one node 4 </p>
  
  <p>Vertical-Line-2: has only one node 2</p>
  
  <p>Vertical-Line-3: has three nodes: 1,5,6 </p>
  
  <p>Vertical-Line-4: has only one node 3</p>
  
  <p>Vertical-Line-5: has only one node 7</p>
  
  <p>Now for the tree</p>
  
  <pre><code>        1            
        /    \
      2        3       
     / \      /  \
    4   5    6    7    
   / \           / \
  8   9        10   11
  </code></pre>
  
  <p>For the above tree , we should get the output each vertical level from top to bottom, and left to right horixontally</p>
  
  <p>8</p>
  
  <p>4</p>
  
  <p>2 9</p>
  
  <p>1 5 6 or 1 6 5 ( since 6 and 5 are at same vertical level, and same HD, order doesn't matter in them)</p>
  
  <p>3 10</p>
  
  <p>7</p>
  
  <p>11</p>
  
  <p>One way to do it is by simply creating a multimap of HD's , and do a level order traversal, and push the values into corresponding HD index .Doing this in level order way will guarantee that we visit from top to bottom vertically .Then print the nodes form lowest HD to highest HD, fulfilling us left to right constraint.</p>
  
  <p>I've read somewhere that we can do it in a better way using Doubly-Link List approach or something similar.Any help people ?</p>