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

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.

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