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\$
3
  • \$\begingroup\$ Are you allowed to use helper functions? \$\endgroup\$
    – coderodde
    Sep 22, 2015 at 16:51
  • \$\begingroup\$ Yes. That would be possible \$\endgroup\$
    – thebenman
    Sep 22, 2015 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\$ Sep 22, 2015 at 19:59

3 Answers 3

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\$
6
  • \$\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, 2015 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\$ Jun 4, 2016 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, 2016 at 6:59
  • \$\begingroup\$ @RajSharma top_view_post_order(root); already handles this. \$\endgroup\$
    – coderodde
    Dec 6, 2016 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, 2016 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\$
0
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\$
2
  • 1
    \$\begingroup\$ What is it you are saying here? Does the OP's code not work for this situation? \$\endgroup\$
    – forsvarir
    Jan 7, 2017 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, 2017 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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