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

}

}

{

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)

## No comments:

## Post a Comment