Top view of binary tree

Problem: Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Write a program to print the top 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 first node at the particular horizontal distance.

Implementation:

#define IntSet std::set<int>

struct NodeDist

{

Node* node;

int horizDist;

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

};

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

std::queue<NodeDist*> nodeDistQ;
IntSet distSet;
nodeDistQ.push(new NodeDist(root, 0));
while(!nodeDistQ.empty())
{
NodeDist* temp = nodeDistQ.front();
if(distSet.find(temp->horizDist) == distSet.end())
{
distSet.insert(temp->horizDist);
std::cout<<temp->node->data<<'\t';
}
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;
}
}

Complexity: O(n)