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...
  • Practice
  • Compete
  • Jobs
  • Leaderboard
  • Hiring developers?
  1. Practice
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

  • Problem
  • Submissions
  • Leaderboard
  • Discussions
  • Editorial

    You are viewing a single comment's thread. Return to all comments →

  • Faland 4 years ago+ 31 comments

    Maybe it needs to add detail about tree representation, i.e. that at any level left subtree never can overlap right subtree and vice versa. In the beginning I was confused - what is expected in following cases:

          1
         / \
        2   3
       / \
      4   5
           \
            6
             \
              7
    

    Expected: 4-2-1-3-7 ? In fact - 4-2-1-3.

          1
         / \
        2   3
       / \
      4   5
         / 
        6
       /
      7
     /
    8 
    

    Expected: 8-4-2-1-3 ? In fact - 4-2-1-3, again.

    303|
    Permalink
    • alex_mistery 4 years ago+ 25 comments

      It is just your visual perseption of the tree! The truth is that mathematically it looks like this:

         ______1 ______
        /              \
       2                3
      / \
      4  5
          \
           6
            \
             7
              \
               8
      
      228|
      ParentPermalink
      • gauthamk 4 years ago+ 2 comments

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

        -15|
        ParentPermalink
        • aminoacid 4 years ago+ 1 comment

          Just as @AlexMistery explained

          -22|
          ParentPermalink
          • amazinghacker 4 years ago+ 3 comments

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

            8|
            ParentPermalink
            • codefornand 4 years ago+ 2 comments

              no only printing of leaves will be added

              -32|
              ParentPermalink
              • aravindprasad 4 years ago+ 2 comments

                This problem expects solution as @AlexMistery explained.

                But the actual Top view seems to be different though.

                16|
                ParentPermalink
                • johnsonjo4531 3 years ago+ 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.

                  5|
                  ParentPermalink
                  • ekjot28 3 years ago+ 1 comment

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

                    0|
                    ParentPermalink
                    • yogeshkaushik008 1 year ago+ 0 comments

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

                      0|
                      ParentPermalink
                  • parmarabhishek_1 2 years ago+ 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);
                        
                    }
                    
                    -13|
                    ParentPermalink
                    • BansheeGhoul 2 years ago+ 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.

                      4|
                      ParentPermalink
                    • digikar99 1 year ago+ 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.

                      2|
                      ParentPermalink
                      • xdavidliu 1 year ago+ 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.

                        4|
                        ParentPermalink
                    • shashikumargund2 11 months ago+ 0 comments

                      it's not working for all the test cases

                      0|
                      ParentPermalink
                    • lishantsahu 10 months ago+ 1 comment

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

                      -1|
                      ParentPermalink
                      • sushils 4 months ago+ 0 comments

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

                        0|
                        ParentPermalink
                  • bennattj 2 years ago+ 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.

                    10|
                    ParentPermalink
                    • archidsouza18 2 years ago+ 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 ?

                      1|
                      ParentPermalink
                      • niranjan_wad 2 years ago+ 5 comments

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

                        1|
                        ParentPermalink
                        • archidsouza18 2 years ago+ 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 ?

                          -1|
                          ParentPermalink
                          • BarryB 2 years ago+ 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.

                            -3|
                            ParentPermalink
                        • bennattj 2 years ago+ 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).

                          1|
                          ParentPermalink
                        • 15A31A0566 11 months ago+ 0 comments

                          Try using TreeMap so the keys will be in sorted order

                          0|
                          ParentPermalink
                        • Sumitkush677 9 months ago+ 0 comments

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

                          0|
                          ParentPermalink
                        • Sumitkush677 9 months ago+ 0 comments

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

                          0|
                          ParentPermalink
                      • bennattj 2 years ago+ 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.

                        1|
                        ParentPermalink
                • pkenil96 2 years ago+ 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!

                  1|
                  ParentPermalink
              • prnvkrjha 4 years ago+ 0 comments

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

                3|
                ParentPermalink
            • euler 2 years ago+ 0 comments

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

              8|
              ParentPermalink
            • sagar_yadav 2 years ago+ 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 :)

              1|
              ParentPermalink
              • tanmax 2 years ago+ 1 comment

                how can you push sometrhing from front in a vector

                0|
                ParentPermalink
                • boolean_bro 10 months ago+ 0 comments

                  vec.push_front(data);

                  0|
                  ParentPermalink
        • phattantran123 3 years ago+ 0 comments

          but if this case1 , the top view not see

          0|
          ParentPermalink
      • trideceth12 4 years ago+ 0 comments

        "truth". If that's a mathematical truth show your proof.

        0|
        ParentPermalink
      • jvedang 4 years ago+ 2 comments

        If you add underscores to root, why not to all elements?

                               ______1______
                              |             |
                        ______2______       3
                       |             |
                       4             5______
                                            |
                                            6______
                                                   |
                                                   7
        

        Isn't the my shown diagram show uniformness according to your design? You just broadened the root, if you broaden the root, you will also have to broaden others equally. So its answer will be 4,2,1,3,7

        Reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

        -12|
        ParentPermalink
        • Mayur_Detroja 3 years ago+ 0 comments

          if you only have same space everywhere how can you add left child of 3, so really parents have twice width of branch then children so all the nodes can be set.

          0|
          ParentPermalink
        • harish_raghav333 2 years ago+ 0 comments

          i have the same question .This case will definitely leads to failure of our logic

          1|
          ParentPermalink
      • Litecoin 3 years ago+ 0 comments

        Mathematically it's what you define it to be, and the exercise's woding is wide open to interpretation.

        3|
        ParentPermalink
      • s0rav 3 years ago+ 0 comments

        really awesome!!

        0|
        ParentPermalink
      • omkardeshpande 3 years ago+ 0 comments

        http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

        4|
        ParentPermalink
      • Aniruddha_ 3 years ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
      • thedurphy 2 years ago+ 2 comments

        @alex_mistery, I understand what you are saying, however, in my experience, top-view of a binary tree is determined by the combination of Level-Order-Traversal and Vertical-Order-Traversal, in other words, you determine all the nodes that are in the same Vertical-Order but only choose the node in each Order that first appears in the Level-Order list. So when doing this, you get the following...

        Level_Order = [1, 2, 3, 4, 5, 6, 7, 8]
        

        Vertical-Orders are the following (0 is root position, all others are delta from root)

        Distance_from_root = -2|-1|0|1|2|3
                              4| 2|1|3|7|8
                               |  |5|6| | 
        

        Since 4, 2, 7, 8 are alone in there set, we don't have to refer to the level order choose. In the 0 and 1 Distances from the root, we have [1,5] and [3,6]. 1 occurs first in Level_order over 5, so we choose 1. 3 occurs first in Level_order over 6, so we choose 3. So after eliminating 5 and 6, going from left-right, we get...

        4, 2, 1, 3, 7, 8
        

        This is the algo used in Geeks for Geeks and is widely used in all documentation of top-view I've seen. So, @Faland is correct in this respect. Intuitively, the alternative where someone only see the higher levels in the top-view without compensating for vertical displacement doesn't make any sense. Think about how a pyramid works. If I were to take @alex_mistery's interpretation, I shouldn't be able to see the outerbricks on the base of a pyramid if I was looking down from the top no matter how far away from the center those bricks were.

        7|
        ParentPermalink
        • victortang_com 2 years ago+ 0 comments

          I watched a video on Youtube giving the same explanation as you did. However, what confused me is why level order traversal should be referred? Why can't we print the first node for each horizontal distance stored in the Vertical Order traversal dictionary (which is the top node of each HD)?

          0|
          ParentPermalink
        • bennattj 2 years ago+ 1 comment

          FYI, there is a problem with this definition. You can have overlap of the "top" nodes. For instance, when looking "to the left", you could have a branch "poke" out that coincides with another branch. In this case both nodes would appear to be at both the same level and height. My assumption (in my solution) for a tie was the the "left-most" branch was the highest--that is the branch that originated from the "most" left position (in this case that would be how I drew it).

          image

          4|
          ParentPermalink
          • mlvl_jr 4 months ago+ 0 comments

            Now, that's some Editorial-grade insight take notes, lads!

            0|
            ParentPermalink
      • fheil0815 2 years ago+ 1 comment

        how the hell is that supposed to be mathematical? mathematically a tree is not even a geometric object. and there certainly is no correct way to draw it.

        23|
        ParentPermalink
        • VirajSingh19 2 years ago+ 0 comments

          agreed :)

          3|
          ParentPermalink
      • jason_goemaat1 2 years ago+ 0 comments

        That's not true, you're changing the tree by making the 6 right of the 5. You need to space out those lower levels so 5->6->7->8 still goes to the left, but the 8 is always right of the 2.

        1|
        ParentPermalink
      • 1998rahular 2 years ago+ 0 comments

        nice explanation

        0|
        ParentPermalink
      • danielvillaseca 2 years ago+ 2 comments

        Thanks, checking the level sign i was able to solve this problem

        void verticalTraversal(node* head, map<int,int> &levelMap, int level) {
            if(head == NULL)
                return;
            if(levelMap.count(level) == 0)
                levelMap[level] = head->data;
            if(level == 0 || level < 0)
                verticalTraversal(head->left, levelMap, level - 1);
            if(level == 0 || level > 0)
                verticalTraversal(head->right, levelMap, level + 1);
        }
        void topView(node * root) { 
            if (root == NULL)
                return;
         
            map<int, int> levelMap;
            verticalTraversal(root, levelMap, 0);
            
            for (map<int,int>::iterator it=levelMap.begin(); it!=levelMap.end(); ++it) {
                cout << it->second << ' ';
            }
        }
        
        -3|
        ParentPermalink
        • mayank___17 8 months ago+ 0 comments

          Doesnt work

          0|
          ParentPermalink
        • ismailashish786 4 months ago+ 0 comments
          [deleted]
          0|
          ParentPermalink
      • AshimGupta 2 years ago+ 1 comment

        Why have you only considered top root like this, why did'nt you made every root level same as the top one ? @Faland is right and geeksforgeeks also refers the same .

        0|
        ParentPermalink
        • vbalakrish67 2 years ago+ 0 comments

          we should have level orders from top(root). So according to this question, we can only consider for root alone.

          0|
          ParentPermalink
      • mirwise001 2 years ago+ 0 comments

        1 / \ 2 3 \ 5 / \ 4 6 \ 7 \ 8

        0|
        ParentPermalink
      • xdavidliu 1 year ago+ 0 comments

        the diagrams of the problem should have been drawn like this in order not to create ambiguity.

        0|
        ParentPermalink
      • xdavidliu 1 year ago+ 0 comments

        note that this is no longer true; the problem has been changed to the exact opposite!

        2|
        ParentPermalink
      • noorulh06 1 year ago+ 0 comments

        According to your explaination, I you are asked to print the bottom view of the tree then it it will print all the elements of the tree because they are all visible from bottom. But I think this will not be right.

        0|
        ParentPermalink
      • dewscoder 1 year ago+ 1 comment

        I coded according to this definition, but the test cases failed except the first one.

        Here is a custom test case that I used 7 10 4 3 5 6 7 11 10 / \ 4 11 / \ 3 5 \ 6 \ 7 According the defninition, the output should be 3 4 10 11, and that is what my program also gives, but when I submit the code, except first test case, all other test cases fails

        0|
        ParentPermalink
        • ab_in123 1 year ago+ 0 comments

          Yeah, the pattern in which they want the output is different from the geeksforgeeks order. The val that is considered there is the horizontal distance, so, here I guess they want the vertical order with the least value of horizontal distance (i.e. the farthest left first).

          1|
          ParentPermalink
      • leaveye 1 year ago+ 2 comments

        I am really confused with the top view definition. And do not agree with this explaination.

        For case:

        15
        1 14 3 7 4 5 15 6 13 10 11 2 12 8 9
        

        It expects:

        2 1 14 15 12
        

        but not:

        1 14 15
        
        4|
        ParentPermalink
        • kvncaldwll 1 year ago+ 0 comments

          exact same issue I am having.

          from what I understand, the top view outputs should be in ascending order. but the expected answers from the tests seem to break this rule.

          2|
          ParentPermalink
        • hnjaman 1 year ago+ 1 comment

          you may check this https://www.youtube.com/watch?v=c3SAvcjWb1E

          2|
          ParentPermalink
          • leaveye 10 months ago+ 0 comments

            Yeah, this is the straightforward definition of top view, and at the beginning I think so too. but some test case, and the above explanation break that.

            I was left for months, so this situation may changed now.

            0|
            ParentPermalink
      • mikutkin 1 year ago+ 0 comments

        In that case, why in test case 2 (input 1 14 3 7 4 5 15 6 13 10 11 2 12 8 9) is the expected output 2 1 14 15 12 and not 1 14 15?

        2|
        ParentPermalink
      • tanmayvijay 12 months ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
      • tanmayvijay 12 months ago+ 1 comment
        void topView(Node * root) {
        
            vector<int> vL, vR;
            Node *t = root;
        
            while(t){
        
                t = t->left;
                if(t) vL.push_back(t->data);
            }
        
            t = root;
        
            while(t){
        
                vR.push_back(t->data);
                t = t->right;
            }
        
            for(int i=vL.size()-1; i>=0; i--) cout<<vL[i]<<" ";
            for(int i=0; i<vR.size(); i++) cout<<vR[i]<<" ";
        
        }
        
        
        
            Can anyone explain why this code doesn't work?
        
        1|
        ParentPermalink
        • josh_greig 4 months ago+ 0 comments

          I think you have the same problem as me with what they mean by top-view but I'd like to point out some tiny improvements to your code.

          Storing outputs in a vector is a pointless inefficiency. You can cout in your loops instead of pushing the values to a vector that prints after.

          1|
          ParentPermalink
      • yhmin84 10 months ago+ 0 comments

        You can use negative-position array for the nodes in root-left and positive-position array for the nodes in root-right. Using queue, BFS can be used with sending relative position to root. If abs(position) is larger than length of the corrensponding array (if position >0, positive-pos arr, if position <0, negative-pos arr), append the value to corresponding array. If BFS is done, the result is reversed(negative-pos arr) + value_at_zero + positive-pos arr.

        0|
        ParentPermalink
      • sarathy_v_krish1 5 months ago+ 1 comment

        C++ solution :

        void topView(Node* root)
            {
                if (!root)  return;
        
                map<Node*, int> hd;
                map<int, int> m;
                deque<Node*> q;
                q.push_back(root);
        
                hd[root]=0;
                m[hd[root]]=root->data;
                while(!q.empty())
                {
                    if (root->left)
                    {
                        hd[root->left] = hd[root]-1;
                        if (!m[hd[root->left]]) m[hd[root->left]] = root->left->data;
                        q.push_back(root->left);
                    }
                    if (root->right)
                    {
                        hd[root->right] = hd[root]+1;
                        if (!m[hd[root->right]]) m[hd[root->right]] = root->right->data;
                        q.push_back(root->right);            
                    }
                    q.pop_front();
                    if (q.size())   root = q.front();
                }
                map<int, int>::iterator it = m.begin();
        
                while(it!=m.end())
                {
                    cout << it->second << " ";
                    it++;
                }
            }
        
        2|
        ParentPermalink
        • saketbharti20171 3 months ago+ 1 comment

          eplain hd[root->data]=root->data; if (!m[hd[root->left]]) m[hd[root->left]] = root->left->data;

          0|
          ParentPermalink
          • sarathy_v_krish1 3 months ago+ 0 comments

            The idea is that for each node traversed, if that node has a horizontal distance(distance from the centre of the tree) which no other node has had so far, map that horizontal distance to the value of that node.

            It goes down the tree and stores the first nodes which are at all the possible distances from the root

            0|
            ParentPermalink
      • pandeysdr16 3 months ago+ 0 comments

        Can't we say print all left most and right most elements of root node ?

        0|
        ParentPermalink
    • marcotuliorr 4 years ago+ 2 comments

      I think Faland is right. This link correctly defines tree top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

      4|
      ParentPermalink
      • Gprinziv 4 years ago+ 1 comment

        Think of it this way, @marcotuliorr. Imagine if that '3' node had three consecutive children "7 - 8 - 9" (each node is the left child of its parent.) Would that branch cross over the long "4 - 5 - 6" branch and make the top-down view of the tree "9 - 2 - 1 - 3 - 6"? Of course not!

        Every node's child must retain the positional properties of its parent, I.E. if 2 is to the left of 1, then 4 and 5 must also be to the left of 1. If 5 is to the left of 1, 6 must be to the left of 1 as well, etc. There's no way a branch not on the leftmost or rightmost path could be visible from the top down.

        3|
        ParentPermalink
        • trideceth12 4 years ago+ 0 comments

          That makes sense. "For all nodes, everything down the right branch is to the node's right; Everything down the left branch is to the node's left."

          It makes sense if you think of it in the context of a binary search tree, and left and right as less than and greater than.

          2|
          ParentPermalink
      • jason_goemaat1 2 years ago+ 0 comments

        I think that link is wrong. In a binary tree, once you go left, all descendants of that child are by definition left of that parent. To get an accurate spatial representation you have to expand your tree so that the bottom level will fit if it is full. They say:

                1
              /   \
            2       3
              \   
                4  
                  \
                    5
                     \
                       6
        Top view of the above binary tree is
        2 1 3 6
        

        But all nodes 'left' of the 1 should be drawn to the left of the 1. If the tree's bottom level was full it would have 16 nodes and it should be drawn that way. If you add a node '7' left of '3' using this representation, it would overlap with the '4'.

        3|
        ParentPermalink
    • Yongping 4 years ago+ 0 comments

      YES, I'm also confused: what's top view......

      3|
      ParentPermalink
    • aravindprasad 4 years ago+ 2 comments

      Dont agree with this problem being tagged as "Easy".

      37|
      ParentPermalink
      • maximshen 3 years ago+ 5 comments

        I actually disagree with your disagree.

        "Top view" is simply defined as, "Starting from top node, every node added to the right side of top node is every right side node's right node if any, every node added to the left side of top node is every left side node's left node, if any." I just used a linkedlist to append left and right nodes on both sides from center to two ends.

        This problem has been completely misleaded by @Faland, unfortunately. And I don't think I am smarter than many folks here, so I kinda curious why this one caused so many confusion.

        4|
        ParentPermalink
        • rajatbarman 3 years ago+ 0 comments

          It caused confusion because GFG defines top view in a different manner than this question. http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

          3|
          ParentPermalink
        • Wafflenaut 3 years ago+ 0 comments

          I think solving it is easy, but finding an elegant solution seems difficult. Not even sure how you'd do it without adding additional functions or creating something fairly icky.

          1|
          ParentPermalink
        • hackmeifyoucan 2 years ago+ 0 comments

          I just read your comment and solved it in 60 sec. Thanks very much :)

          0|
          ParentPermalink
        • BansheeGhoul 2 years ago+ 5 comments

          This question is just about printing the outermost left or right nodes .. java code (its a version of what parmarabhishek_1 told https://www.hackerrank.com/challenges/tree-top-view/forum/comments/331313 )

          java code

          void travLeft(Node root){
              if(root.left!= null)
                    { travLeft(root.left);}
                 System.out.printf("%d ",root.data);
                         }
              void travRight(Node root){
               System.out.printf("%d ",root.data);
               if(root.right!= null){
                   travRight(root.right);}
              }
          
             void topView(Node root) {
                 if(root.left != null){
                              travLeft(root.left);
                                      }
                    System.out.printf("%d ",root.data);
                 if(root.right != null){
                              travRight(root.right);
                                      }      
              }
          
          -4|
          ParentPermalink
          • h415074476 2 years ago+ 1 comment

            you are right.

            -1|
            ParentPermalink
            • BarryB 2 years ago+ 0 comments

              Actually the problem being tested with the test cases is easy. However if you try to solve the problem as defined in GFC, I'd agree that it's not that easy. I actually spent some time trying to solve what GFC describes, but I couldn't get all the test cases to work. When I debugged some of the test cases, I realized that the test cases were all for the simplified case. I then modified my code to support that, and all test cases passed.

              After I got all the test cases to work, I actually looked at the editorial, and found the following.

              Note: This solution is overly simplified and you will need something more complicated for certain types of imbalanced trees.

              Basically the actual problem statement was not well defined. Either the test cases should support all types of trees, and the problem could potentially be made a medium problem. Or the note should have been put in the problem statement, instead of the editorial.

              0|
              ParentPermalink
          • mvbelgaonkar 1 year ago+ 0 comments
            [deleted]
            0|
            ParentPermalink
          • adityaverma82191 1 year ago+ 0 comments

            this will only pass the 1st test case. i thougth the same logic and i implemented it in c++.

            1|
            ParentPermalink
          • kyxap 1 year ago+ 0 comments

            Will not pass the 2nd TCs :)

            1|
            ParentPermalink
          • ioluwayo 4 months ago+ 0 comments

            This only passes the sample and first test case

            0|
            ParentPermalink
        • jschopick 2 years ago+ 0 comments

          I did this using helper functions and recursion but I printed the left values before the recursive call so it printed in reverse order. I thought I was just fundamentally wrong but I read this comment and then looked at my code in more detail and I just printed after the recursive call and it worked. Thank you!

          0|
          ParentPermalink
      • tvanloon 3 years ago+ 1 comment

        took me two minutes to solve

        -59|
        ParentPermalink
        • edemohankrishna1 2 years ago+ 1 comment

          can you please send me the code Mr tvanloon.I am basic coder please....:)

          0|
          ParentPermalink
          • iam_ghanshyam 2 years ago+ 0 comments

            Its better(learning-wise) to ask for a problem-solving approach instead of solutions.

            2|
            ParentPermalink
    • jogi9045 3 years ago+ 0 comments

      8 4 2 1 3

      0|
      ParentPermalink
    • akashBhayekar 3 years ago+ 1 comment

      This problem dosent consider these much cases, it only want you to print left only list and right only list. which can be simply achieved by going extreme left and extreme right. so yeah second is correct for this problem.

      -2|
      ParentPermalink
      • b0kater 2 years ago+ 0 comments

        The issue is that the problem is poorly defined. You are correct, but that isn't clear from the problem statement.

        6|
        ParentPermalink
    • pkenil96 2 years ago+ 0 comments

      I don't think thats how it is!! According to me the output should rather be : 8 4 2 1 3.. I think all we need is to calculate the horizontal distance of each nodes from the root node and print the node and store them in the queue..then print the first node from the queue for each level of horizontal distance!

      0|
      ParentPermalink
    • panda_whisperer 2 years ago+ 0 comments

      Had the same expectation after reading the problem statement. Glad I came here before wasting a bunch of time and getting frustrated.

      I agree the problem statement needs more examples.

      3|
      ParentPermalink
    • desaim 2 years ago+ 0 comments

      Thanks. My submission failed but when I looked into why it was pretty clear I only a vague/foggy notion of 'top view'.

      0|
      ParentPermalink
    • parmarabhishek_1 2 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • hammeramr 2 years ago+ 0 comments

      Thank you I didnt want to cheat but this makes the problem much easier.

      0|
      ParentPermalink
    • thedurphy 2 years ago+ 0 comments
      [deleted]
      0|
      ParentPermalink
    • EmberQuill 2 years ago+ 0 comments

      Yeah, some more details would be nice, or perhaps using a tree like the OP's examples as one of the problem examples to demonstrate exactly what is meant by "top view". Or just a definition of "top view". I spent quite a while working on a solution that would track how far left and right of center each node was in order to handle a case like the examples above. Then I checked the discussion and realized the problem was way easier than I'd thought.

      0|
      ParentPermalink
    • Scipsycho 2 years ago+ 0 comments

      yeah but technically in your second example it should be 8-4-2-1-3. I am scratching my head for a very long time , they should really add more explanation

      void topView(node * root,int fact=0,int lcomp=1,int rcomp=-1) {
          
          if(root==nullptr)
              return;
          
          cerr<<root->data<<": "<<lcomp<<" ' "<<fact<<" ' "<<rcomp<<endl;
          if((fact>rcomp) || (fact<lcomp)){
              cout<<root->data<<" ";
              if(lcomp>rcomp){
                  rcomp++;
                  lcomp--;
              }
              else if(fact>rcomp)
                  rcomp++;
              else if(fact<lcomp)
                  lcomp--;
              
              
              
          }
          topView(root->left,fact-1,lcomp,rcomp);
          topView(root->right,fact+1,lcomp,rcomp);
      }
      
      -1|
      ParentPermalink
    • armagedescu 2 years ago+ 0 comments

      I agree with @Faland. The problem is not well described. So, first I searched the internet for top view problem and solved it. https://www.youtube.com/watch?v=c3SAvcjWb1E In fact a correctly solved problem failed the test case. So, I calculated manually and my solution was correct. It took me lot of time to understand that there is meant something else, after looking in this discussion. So, the problem here is not correctly described. Here is also info about top view: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/ Don't cover you with mathematical description. Look through the window, see a tree. What will be the top view of a tree if you cut a branch? Don't cover you with the fact that you can't provide a mathematical description. An algorithm is already a mathematical description, see youtube link. Any tree that is seen through the windows is all maths.

      2|
      ParentPermalink
    • jason_goemaat1 2 years ago+ 0 comments

      That is just an artifact of how you draw the tree. By definition, everything left of the 1 is left of the 1. To accurately draw your tree, the 3 needs to be right of the 1 and all nodes in the left branch from the 1 should be displayed left of the 1.

      This isn't easy to see in the examples because you have a sparse tree, but if you leave enough rooms for the bottom level to be full, you can see why:

                     1
                    / \
                   /   \
                  /     \
                 /       \
                /         \
               /           \
              /             \
             2               3
            / \             / \
           /   \           /   \
          /     \         /     \
         4       5       X       X
        / \     / \     / \     / \
       X   X   6   X   X   X   X   X
      

      If you go on and add 7 left of 6 and 8 left of 7, you add two new levels to the tree, and you'll have to space it out to handle all the other nodes possible at that level. No matter what you do, everything right of the 2 will be right of the 2, and left of the 1, being shaded to the link from 1 to 2.

      5|
      ParentPermalink
    • Dhaminimohandas 2 years ago+ 0 comments

      Since the question mentions it is a binary tree, this possibility is ruled out. chect out this link for the properties of binary trees.

      http://cs-study.blogspot.in/2012/11/properties-of-binary-tree.html

      1|
      ParentPermalink
    • weiyanen 2 years ago+ 0 comments

      Yes, I have the same comfusion. And I write a code below: void topView(Node root) { if(root!=null) { Set s = new HashSet(); LinkedList queue = new LinkedList(); Map map = new HashMap(); queue.offer(root); map.put(root.data, 0); while(!queue.isEmpty()) { Node node = queue.poll(); Integer shadow = map.get(node.data); if(!s.contains(shadow)) { System.out.print(node.data + " "); s.add(shadow); } if(node.left != null) { queue.offer(node.left); map.put(node.left.data, shadow-1); } if(node.right != null) { queue.offer(node.right); map.put(node.right.data, shadow+1); } } } }

      0|
      ParentPermalink
    • octavianarsene 2 years ago+ 0 comments

      Very important details and see the below alex_mistery's comment!

      0|
      ParentPermalink
    • evhen14 2 years ago+ 0 comments

      LOL. I solved it for the graphical case first and thought that it was at least medium level problem. Now I see that it's a simpler problem. Thanks @Faland

      0|
      ParentPermalink
    • HHWWHH 2 years ago+ 2 comments

      I am a beginner. If I found this place earlier, I would have not spent hours on this unclarified 'easy' question and doubt myself...... In conclusion, two interpretations on this question: 1. Just like what @thedurphy said, this interpretation of top view aligns with this Youtube video and GFG. And code in Python can be like this (Although it does not pass all tests, it aligns with first interpretation):

      def topView(root):
          from collections import defaultdict
          queue=[(root,0)]
          hashtable=defaultdict(lambda:[]) 
          for node,level in queue: #level=x-coordinator
              if node!=None:
                  hashtable[level].append(node.data) #hashtable, collect node data with the same level#
                  queue.extend([(node.left,level-1),(node.right,level+1)]) #add node in sublevel to queue
          if hashtable !=None:
              for level in xrange(min(hashtable.keys()),max(hashtable.keys())+1):
                  print hashtable[level][0], #TOPVIEW
          else:
              return None
      
      1. Another interpretation is provided by @trideceth12, which is aligned with all test cases. Although I doubt this interpretation, I still created the Python code for it:
      def topView(root):
          #start with left most leaf
          if root.left:
              printleftside(root.left) #print left side top view, from bottom to top (left to right)
          print root.data, #print root
          if root.right:
              printrightside(root.right) #print right side top view, from top to bottom (left to right)
      
      def printleftside(node):
          if node:
              printleftside(node.left)
          else:
              return
          print node.data,
      
      def printrightside(node):
          if node:
              print node.data,
              printrightside(node.right)
          else:
              return
      

      In the end, WHAT do we use TOPVIEW for in terms of both interpretations?

      0|
      ParentPermalink
      • nirajkamdar27 6 months ago+ 0 comments
        [deleted]
        0|
        ParentPermalink
      • nirajkamdar27 6 months ago+ 0 comments

        your code is just passing first test https://pastebin.com/CmTWX5C1

        0|
        ParentPermalink
    • tfccomputation 2 years ago+ 1 comment

      My solution

      void topViewL(node * root) {
          if(!root) return;
          topViewL(root->left);
          printf("%d ",root->data);
      }
      
      void topViewR(node * root) {
          if(!root) return;
          printf("%d ",root->data);
          topViewR(root->right);
      }
      
      void topView(node * root) {
          topViewL(root);
          topViewR(root->right);
      }
      
      -10|
      ParentPermalink
      • Blacku 1 year ago+ 0 comments

        this code is only passing the test case 1

        0|
        ParentPermalink
    • vipulvikram 1 year ago+ 1 comment

      here top view means:==>>

              ↗↘
           ↗       ↘
       ↗              ↘
      
      first print from left straight bottom to root and then straight right downword.
      
      -3|
      ParentPermalink
      • vipulvikram 1 year ago+ 0 comments

        Enjoy..

        0|
        ParentPermalink
    • TarunSikka 1 year ago+ 1 comment

      The problem has been changed now . New ans for above would be as expected i.e., 4-2-1-3-7

      1|
      ParentPermalink
      • sam_littlefair 1 year ago+ 0 comments

        I feel like this makes the problem quite a bit harder, I don't think it should still be marked as "easy".

        2|
        ParentPermalink
    • rishabhagarwal19 1 year ago+ 0 comments

      Thanks a lot Faland. People confuse for this representation. I retried this question after 3 years and again forgot.

      0|
      ParentPermalink
    • hisaravanankesa1 1 year ago+ 0 comments

      Yes it should be based on horizontal distance from root node. Refer to https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/

      0|
      ParentPermalink
    • MinhThai2 11 months ago+ 0 comments

      Thanks for the small examples to visualize. This help alot.

      This problem looks like we need to generate horizontal, depth pair for each node, then group them by horizontal coordinate, and just collect the minimum depth from each group.

      For problem statement:

      1 (0, 0) 2 (1, 1) 5 (2, 2) 6 (3, 3) 3 (1, 3) 4 (2, 4)

      1 (0, 0)

      2 (1, 1) 3 (1, 3)

      5 (2, 2) 4 (2, 4)

      6 (3, 3)

      solution pass all test cases

      0|
      ParentPermalink
    • deepamgupta 7 months ago+ 0 comments

      If we take the tree as in Faland's comment.

            1
           / \
          2   3
         / \
        4   5
             \
              6
               \
                7
      

      The answer for which the compiler successfully runs the test is 4-2-1-3-7

      and for

            1
           / \
          2   3
         / \
        4   5
           / 
          6
         /
        7
       /
      8 
      

      output is 8-4-2-1-3 which compiler accepts.

      You may refer geeks for geeks for the top view.

      1|
      ParentPermalink
    • tat_lim 6 months ago+ 0 comments

      Java Solution in O(n)

      // where n is the number of nodes in the binary tree
      public static void topView(Node root) {
          int MAX = 500;    // Otherwise, MAX=getNodeCount(root);
          int[] top = new int[MAX*2];
          Queue<Object[]> queue = new ArrayDeque<>();
          queue.add(new Object[]{root, MAX});
          while(!queue.isEmpty()) {
              Object[] array = queue.remove();
              Node node = (Node)array[0];
              Integer order = (Integer)array[1];
              if(node == null) continue;
      
              if(top[order] == 0) top[order] = node.data;
              queue.add(new Object[]{node.left, order-1});
              queue.add(new Object[]{node.right, order+1});
          }
      
          for(int data: top) if(data != 0) System.out.print(data + " ");
      }
      
      3|
      ParentPermalink
    • imjunqing 5 months ago+ 0 comments

      Here's the Java code, I used the approach from geekstogeeks. I think the question did not specifiy and clearly define what a top view is. The correct implementation which passes all test cases should be according to this https://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/.

      public static void topView(Node root) {
              Dictionary<Node, Integer> dictionary = new Hashtable<>();
              Map<Integer, Node> topResult = new TreeMap<>();
              Queue<Node> nodes = new LinkedList<>();
      
              if (root != null) {
                  topResult.put(0, root);
                  dictionary.put(root, 0);
                  nodes.add(root);
              }
      
              while (!nodes.isEmpty()) {
                  Node current = nodes.remove();
                  int currentOrder = dictionary.get(current);
      
                  if (current.left != null) {
                      int value = currentOrder-1;
      
                      if (!topResult.containsKey(value)) {
                          topResult.put(value, current.left);
                      }
                      dictionary.put(current.left, value);
                      nodes.add(current.left);
                  }
      
                  if (current.right != null) {
                      int value = currentOrder+1;
      
                      if (!topResult.containsKey(value)) {
                          topResult.put(value, current.right);
                      }
                      dictionary.put(current.right, value);
                      nodes.add(current.right);
                  }
              }
      
              for (Node node : topResult.values()) {
                  System.out.print(node.data + " ");
              }
          }
      
      0|
      ParentPermalink
    • pranav_gautam82 2 months ago+ 0 comments

      You understand ,in this question we are talking about Binary tree?? What kind of explanation have you given here??

      0|
      ParentPermalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature