**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)

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

ReplyDelete