# Traversal of a tree in a top-view order

I was trying to solve this problem.

Problem Statement

You are given a pointer to the root of a binary tree. Print the top view of the binary tree. You only have to complete the function.

For example :

3
/   \
5     2
/ \   / \
1   4 6   7
\       /
9     8
Top View : 1 -> 5 -> 3 -> 2 -> 7


I figured that the answer could be obtained by keeping on going till the leftmost node recursively and then traverse the tree till the rightmost node from the root.

Although I have managed to solve this problem I feel that my solution is just a little hack and not the best possible solution. The function I had written is

/*
struct node
{
int data;
node* left;
node* right;
};

*/
void top_view(node * root)
{
static node* temp = root;
if(root == NULL)
{
return;
}
top_view(root->left);
cout<<root->data<<" ";
if(root == temp)
{
root = root->right;//Don't want to print the root element twice
while(root != NULL)
{
cout<<root->data<<" ";
root = root->right;
}
}
}

• Are you allowed to use helper functions? – coderodde Sep 22 '15 at 16:51
• Yes. That would be possible – thebenman Sep 22 '15 at 16:55
• The challenge is, in my opinion, ill-defined. How widely are the nodes spaced? (Note that the "5"-"3"-"2" nodes are spaced out differently from the "1"-"5"-"4" nodes.) How many generations of left-children of the "8" node are necessary until something peeks out from beneath the shadow of the "1"? – 200_success Sep 22 '15 at 19:59

You can define two helper functions: one traverses the leftmost branch using post-order and another one traverses the rightmost branch using pre-order. See what I mean:

static void top_view_post_order(node* root)
{
if (!root) return;

top_view_post_order(root->left);
cout << root->data << " ";
}

static void top_view_pre_order(node* root)
{
if (!root) return;

cout << root->data << " ";
top_view_pre_order(root->right);
}

void top_view(node * root)
{
top_view_post_order(root);
top_view_pre_order(root->right);
}


The above passed the hackerrank's test.

Edit: What comes to static fields in functions, most books suggest that their presence is an indicator of a design flaw; don't do them - pass some structure to the function as "state information". Also, if you were to write multithreaded code, there is a great potential for data races as well.

• Thanks. Looks a lot cleaner. Anyways, my question was really regarding the the usage of static variable in my code. Any comments on that? – thebenman Sep 22 '15 at 17:03
• But this doesn't handle this type: See the 2nd example in geeksforgeeks.org/print-nodes-top-view-binary-tree – Nikhil Verma Jun 4 '16 at 8:39
• System.out.print(root.data+" "); this was missing from your code. put this in between top_view_post_order(root); top_view_pre_order(root->right); – RajSharma Dec 6 '16 at 6:59
• @RajSharma top_view_post_order(root); already handles this. – coderodde Dec 6 '16 at 7:40
• @coderodde I dont know when I tried you code it didn't print the top root data and once I added it worked. – RajSharma Dec 6 '16 at 9:55

you can also use a variable to tell the direction in which you are recursing through the tree; you are interested in only the left nodes on the left side and the right nodes on the right side:

void rec(node*root, int direction)
{
if (!root)
return;
if (direction ==0)
{
rec(root->left, 0);
cout << root->data <<" ";
}
else
{
cout << root->data <<" ";
rec(root->right, 1);
}
}

void top_view(node * root)
{
rec(root->left,0);
cout << root->data <<" ";
rec(root->right,1);
}


Consider this case, if the tree is not complete binary tree:

    1
/   \
2       3
\
4
\
5
\
6


Top view of the above binary tree is 2 1 3 6

• What is it you are saying here? Does the OP's code not work for this situation? – forsvarir Jan 7 '17 at 18:27
• Nope, all the above given solutions will not work for this tree. If u have a doubt, try it. – mangu Jan 8 '17 at 3:00