Tuesday, May 5, 2015

Bottom view of binary tree

Problem: Bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom. Write a program to print the bottom view of a binary tree.

Approach: Do level order traversal of given binary tree and calculate horizontal distance of each node and then print only the last node at the particular horizontal distance.

Implementation:

#define mapIntToInt std::map<int, int>

struct NodeDist
{
Node* node;
int horizDist;
NodeDist(Node* nd, int hd):node(nd), horizDist(hd){}
};

void BSTree::bottomView()
{
if(!root)
return;

std::queue<NodeDist*> nodeDistQ;
mapIntToInt mapDistToNode;
nodeDistQ.push(new NodeDist(root, 0));
while(!nodeDistQ.empty())
{
NodeDist* temp = nodeDistQ.front();
mapDistToNode[temp->horizDist] = temp->node->data;
if(temp->node->left)
nodeDistQ.push(new NodeDist(temp->node->left, temp->horizDist - 1));
if(temp->node->right)
nodeDistQ.push(new NodeDist(temp->node->right, temp->horizDist + 1));
nodeDistQ.pop();
delete temp;
}

for(mapIntToInt::iterator it = mapDistToNode.begin(); it != mapDistToNode.end(); ++it)
{
std::cout<<it->second<<'\t';
}
}

Complexity: O(n)

No comments:

Post a Comment