The 9, 10, and 11 nodes are all to the right of the 1 node. If the 1 node had a left child, 12, it's right child would be 13, not 10. You have to expand the tree horizontally for each additional level the tree.

Your example is not a binary tree. void top_view_dir(node *root, int dir) { if(root != NULL) { if(dir) { top_view_dir(root->left, 1); printf("%d ", root->data); } else { printf("%d ", root->data); top_view_dir(root->right, 0); } } } void top_view(node * root) { if(root == NULL) { return; } else { top_view_dir(root->left, 1); printf("%d ", root->data); top_view_dir(root->right, 0); } }

Exactly. I am looking for a perfect soluction for this problem.

Provided solution doesn't work if we don't want to modify our tree, right? IMHO usually if want to print some elements in some container it is always better not to modify this container...

Awesome!!!

And it produces memory leaks!

I really like the simplicity and efficiency of your solutions, bravo.

Thanks man...!

almost same solution as joethomas89. Basic idea is first travell along the left side of the tree till the last node by incrementing gh var from the child of root and while returning back decrement till root so that gh value will be one less than the initial value of prog. When gh==0 means left side and root are visited now start visiting only the right side. While travelling right side it will not travell left side as we have put consdition gh>=1 and it will be true only at the begginng while travelling left side from the root.

int gh=1;

void top_view(node * root) { if(root->left!=NULL && gh>=1){ ++gh; top_view(root->left); printf("%d ",root->data); --gh; } else if(gh>=1){ printf("%d ",root->data); --gh; return; }

if(gh==0)
{
    if(root->right!=NULL){
    printf("%d ",root->right->data);
    top_view(root->right);

    }
    else{
        return;
    }   
}

}

Excellent thinking. Making the right node null. I am kicking myself for not thinking of this before.

i think you alter the tree;,my answer:

void top_view(node * root)
{
    node * tmp = NULL;
    if(root->left){
        tmp = root->left->right;
        root->left->right = NULL;
        top_view(root->left);
        root->left->right = tmp;
    }
    cout<<root->data<<" ";
    if(root->right){
        tmp = root->right->left;
        root->right->left = NULL;
        top_view(root->right);
        root->right->left = tmp;
    }
    return;
}

i think provided solution will not work if left subtree have a right nodes in such a way that all the nodes go past right subtree or vice versa.

That would kill this scenario:

    1
  /   \
2       3
  \   
    4  
      \
        5
         \
           6

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

I came up with a similar solution in Java :) So far, I like it the most.

void top_view(Node root)
{
    top_view(root, 0);
}

void top_view(Node root, int side)
{
    if (root != null) {
        if (side <= 0) {
            top_view(root.left, -1);
        }
        
        System.out.print(root.data + " ");
        
        if (side >= 0) {
            top_view(root.right, 1);
        }
    }
}

The most clever solution I found here :)

I dont think your solution would work if node 6(sample input) had a child in the left or right. Your solution would just skip 6 altogether and print 7 only.

Thanks, theses conditions made my submission correct(and i know why)... i used unordered_map to do the same.

oh my god! how did u think ?