Traversal of a tree in a top-view order

Question

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

• coderodde: Are you allowed to use helper functions?
• thebenman: Yes. That would be possible
• 200_success: 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"?

Answer 1

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.

• thebenman: Thanks. Looks a lot cleaner. Anyways, my question was really regarding the the usage of static variable in my code. Any comments on that?
• Nikhil Verma: But this doesn't handle this type: See the 2nd example in geeksforgeeks.org/print-nodes-top-view-binary-tree
• RajSharma: 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)
• coderodde: @RajSharma top_view_post_order(root); already handles this.
• RajSharma: @coderodde I dont know when I tried you code it didn't print the top root data and once I added it worked.

Answer 2

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);
}

Answer 3

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

• forsvarir: What is it you are saying here? Does the OP's code not work for this situation?
• mangu: Nope, all the above given solutions will not work for this tree. If u have a doubt, try it.