Coders Packet

C++ code for top view of a binary tree

By Rishita

It is a C++ code with explanation for printing the top view of binary tree. Top view of a binary tree is the set of nodes visible when the tree is viewed from the top.

The top view of a binary tree means the nodes which are visible to our eyes when viewed from the top. And in this code, I have written a C++ code to get the top view of the binary tree.

First, we declare a struct Node that has members like data, left pointer, and right pointer.

Then there are the following functions.

1.)Node*newnode(): This function has value as an argument. It returns a new node having Val as its data and sets its left and a right pointer to NULL.

2.)Node*buildTree(): This function is used to build the tree and in most cases this function is pre-built.

3.) vector topView(Node *root): This is the function that returns a vector containing the top view of the tree. If the root is NULL it returns an empty vector, else we declare a map (mp, visited) and a queue. The map visited marks the horizontal distance of the nodes which are visited. And the map mp stores the data of the node which comes first at horizontal distance x. And for the queue, contains pair where the first part contains the node and the second part contains an integer denoting the horizontal distance from the root. Like, the horizontal distance of the root node from the root is 0. And as we move towards the left the horizontal distance of the node decreases by one and moving on the right it increases by one. We first push the root node along with its horizontal distance of 0 in the queue.

Then until the queue is empty the while loop goes on. In each iteration, it pops its front node and if that horizontal distance is unvisited that is it is the first node at that distance then we make it visited and store its node value in map mp where its horizontal distance is key. And then we push its left and right child if they are not NULL. The horizontal distance decrease by one for the left child and increases by one for the right child. The key point to getting the top view is that the node which comes first at a particular horizontal distance will be in the output.

4.) the Main function: In this, it takes test cases and the rest of the input field required to build the tree.

Below is an example of the top view of the binary tree.

    /     \
   2       3
  /  \    /   \
8    5  6    9    

The top view of the above binary tree is
8 2 7 3 9

Download Complete Code


No comments yet