Vertical order traversal of binary tree

Problem: Given a binary tree, print it vertically.

Example:

           12              

         /      \            

      10       30         

      /  \        / \        

     8  11  25  40     

      \           \     \     

       9        28   50  

             

The output of print this binary tree vertically will be:
8
10 9
12 11 25
30 28
40
50

Solution: Using preorder traversal, we can recursively calculate horizontal distances. For every horizontal distance we maintain a list of nodes in hash. 

Horizontal distance (hd) of root is 0, a left edge is considered as -1 and right edge as +1 horizontal distance. For example in the given example tree the hd of 8 is -2, hd of 11 is 0 and hd of 50 is +3.

Implementation:

#define mapIntToIntVect std::map<int, std::vector<int>>

void BSTree::verticalOrder(Node *node, int horizDist, mapIntToIntVect& mapDistToNodesVect)

{

if(!node)

return;

mapDistToNodesVect[horizDist].push_back(node->data);

verticalOrder(node->left, horizDist - 1, mapDistToNodesVect);

verticalOrder(node->right, horizDist + 1, mapDistToNodesVect);

}

void BSTree::verticalOrder()

{

int hd = 0;

mapIntToIntVect mapDistToNodesVect;

verticalOrder(root, hd, mapDistToNodesVect);

std::map<int, std::vector<int>>::iterator it;

for(it = mapDistToNodesVect.begin(); it != mapDistToNodesVect.end(); it++)

{

for(int i = 0; i < it->second.size(); ++i)

{

std::cout<<it->second[i]<<'\t';

}

std::cout<<std::endl;

}

}

Complexity: O(n)