4
\$\begingroup\$

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;
      }
   } 
}
\$\endgroup\$
  • \$\begingroup\$ Are you allowed to use helper functions? \$\endgroup\$ – coderodde Sep 22 '15 at 16:51
  • \$\begingroup\$ Yes. That would be possible \$\endgroup\$ – thebenman Sep 22 '15 at 16:55
  • \$\begingroup\$ 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"? \$\endgroup\$ – 200_success Sep 22 '15 at 19:59
3
\$\begingroup\$

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.

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

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);
}
\$\endgroup\$
1
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.