Tuesday, May 5, 2015

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)

1 comment:

  1. You can also use heap data structure with horizontal distance as the priority of the element. Let me know what you think.

    ReplyDelete