We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

  • gauthamk + 2 comments

    when top view of the tree is asked, which one is meant among the two?

    • aminoacid + 1 comment

      Just as @AlexMistery explained

      • amazinghacker + 3 comments

        If the other was true, it would be much tougher to code. Isn't that?

        • codefornand + 2 comments

          no only printing of leaves will be added

          • aravindprasad + 2 comments

            This problem expects solution as @AlexMistery explained.

            But the actual Top view seems to be different though.

            • johnsonjo4531 + 3 comments

              When I visited this question there was no definition for top view given so I had to search for a definition. I came to the geeks for geeks link that others have referenced and made my algorithm according to geeks for geeks' definition which is the same as @Faland's and it was still accepted no problem. There was also only two test cases when I submitted. I honestly think you can submit either way and be fine unless my submission is not implementing geek for geek's definition of top view correctly.

              • ekjot28 + 1 comment

                If we follow algo given by geeksforgeeks then it doesnt give right answer. Geeks for geeks alfo print according @Faland

                • yogeshkaushik008 + 0 comments

                  It Does, I have submitted the logic of vertical order traversal.

              • parmarabhishek_1 + 4 comments

                This is the actual code for top view of a tree :

                typedef pair<int,int> v_h; 
map <int,v_h> m; // map
map <int, v_h> :: iterator itr; //itterator

void store_view(node * root,int i,int h)
    {
    if(root==NULL)
        return;
    itr=m.find(i);
    if(itr==m.end())
        m[i]=make_pair(h,root->data);
    else
    {
        if(itr->second.first > h)
            m[i]=make_pair(h,root->data);
    }
    if(root->left!=NULL)
        store_view(root->left,i-1,h+1);
    if(root->right!=NULL)
        store_view(root->right,i+1,h+1);
     
}

void print_map()
    {
    for(itr = m.begin(); itr != m.end(); ++itr)
        cout<<itr->second.second<<" ";
}

void topView(node * root)
{
   store_view(root,0,0);
   print_map();
    return;
}

                but the problem demands the top view according to the root node only :

                void for_left(node * root)
{
    if(root->left!=NULL)
        for_left(root->left);
    cout<<root->data<<" ";
}


void for_right(node * root)
{
    cout<<root->data<<" ";
    if(root->right!=NULL)
        for_right(root->right);
}

void topView(node * root)
{
    if(root->left!=NULL)
        for_left(root->left);
    cout<<root->data<<" ";
    if(root->right!=NULL)
        for_right(root->right);
    
}
                • BansheeGhoul + 0 comments

                  You are spot onn in identifying two different implementations .. looks like this question demands just the outer values of the tree. Thanks once again.

                • digikar99 + 1 comment

                  Isn't it the second solution that is expected - the first solution passes in July '18! Seems like they changed the meaning; and if so, I don't think this is a "easy" problem - a "medium" one.

                  • xdavidliu + 0 comments

                    it seems the second part of parmarabhishek_1's post was what the problem originally expected, and that was incorrect. They changed it to correctly require the solution in the first part, as you pointed out. They should have also used a better example to illustrate this subtle point.

                • shashikumargund2 + 0 comments

                  it's not working for all the test cases

                • lishantsahu + 1 comment

                  I think you are printing root->data 3 times in the topView() function.

                  • sushils + 0 comments

                    no he cancelled out repetitions by using root->left and root->right as initializers in the two functions

              • bennattj + 1 comment

                Yep, the definition of "Top-View" was never presented in this problem. Besides the grammatical errors in the sentence "explaining" top-view, it almost literally says: when you view from the top, you'll see the top view.

                The definition I found, that made sense was from the geeks for geeks link. So I solved it that way. I failed everything past the first test. So I looked at the input/output for the second test case.

                For anyone interested, it's clear that the input is given as a binary search tree. So I constructed the graph from the input, ran my program, got the correct result but with extras (to the right for the second test case).

                Then figured I was getting extras because a subtree was "poking" out and they didn't want that. So deleted all of my (more complicated) code for what amounted to a trivial problem.

                • archidsouza18 + 2 comments

                  can anyone explain how to represent the tree for this input, 47 2 40 20 38 30 14 28 10 16 19 44 39 27 7 9 31 12 43 21 5 41 34 49 13 33 3 4 25 22 29 15 32 35 6 24 23 26 1 11 42 36 37 17 18 8 45 48 50 46 ? what is root of this tree ?

                  • niranjan_wad + 5 comments

                    same question.. Expected output: 1 2 47 49 50 My output: 47 2 1 49 50

                    • archidsouza18 + 1 comment

                      @niranjan_wad how did you manage to find the output? Since, it does not tell what is your output. do you know what is root of above question ?

                      • BarryB + 0 comments

                        If you hover of the submission results that failed, there will be a popup that appears, where you can download both the input and expected output for that test case.

                    • bennattj + 0 comments

                      You appear to have the correct output, but in the wrong order. The solution wants it "left-to-right" (which just so happens to be least-to-greatest since these are apparently binary search trees).

                    • 15A31A0566 + 0 comments

                      Try using TreeMap so the keys will be in sorted order

                    • Sumitkush677 + 0 comments

                      bro..first print traverse, then print that node. then u get correct order

                    • Sumitkush677 + 0 comments

                      first traverse,the print that node. u get correct order

                  • bennattj + 0 comments

                    The root is 47 (the first node given), the rest are input as a binary search tree, which means 2 is the left child of 47. 40 is the right child of 2 (because it's less than 47 but greater than 2), 20 is the left child of 40 (less than 47, greater than 2, and less than 40)...etc.

            • pkenil96 + 0 comments

              Exactly!! Even i got that the other way.. I coded the solution considering the horizontal distances of the nodes and all my test cases(except the sample case) failed! The actual top view certainly is different than what they expects!

          • prnvkrjha + 0 comments

            No! an entire branch could appear in the top view. not just the leaves.

        • euler + 0 comments

          Not much tough though. I wrote the code with that assumption only. Problem writers need to do a better job here.

        • sagar_yadav + 1 comment

          no , by the way it become more easy that way u just have to traverse left and store all in vector(push tis data from front) then just traverse right and store it in same vector(push this data from back) then simply print the data or u can use recurssion :)

          • tanmax + 1 comment

            how can you push sometrhing from front in a vector

            • boolean_bro + 0 comments

              vec.push_front(data);

    • phattantran123 + 0 comments

      but if this case1 , the top view not see