• + 3 comments

    Hackers beware! It appears that there was a major change in this problem (in the underlying test cases and checking, but sadly the problem description is highly ambiguous!) and it is no longer sufficient to print the left and right spines. This also invalidates most of the most upvoted comments and answers in this thread from 2-3 years ago. In my opinion, this problem should be labelled Medium or Hard, not Easy!

    To pass all test cases, you must keep track of the locations of every note in the entire tree, assuming all edges are of the same length and same angle. Hence, nodes may show up in the top view even if they are not in a spine!

    Here's a C++ solution that passes all test cases as of July 2018:

      using TopTable=map<int, pair<unsigned,int>>;
      void compute_table_entries(Node *nd, int xpos, unsigned depth, TopTable &tab){
        if(nd){
          auto it=tab.find(xpos);
          if(it!=tab.cend() && depth < it->second.first){
    	  it->second = {depth,nd->data};
    	}else{ tab.insert({xpos, {depth, nd->data}}); }
          compute_table_entries(nd->left, xpos-1, depth+1, tab);
          compute_table_entries(nd->right, xpos+1, depth+1, tab);
        }
      }
      void topView(Node * root) {
        TopTable tab;
        compute_table_entries(root,0,0,tab);
        for(auto entry: tab){
          cout << entry.second.second << ' ';
        }
      }
    
    • + 0 comments

      Looks like you made it through, from the previous comments heard that even editorial solutions isn't passing the test cases #strange.

    • + 11 comments

      Under 10 lines of code C++ solution

      Actually there's no need to keep track of depth or to use another function, here's an example solution:

      void topView(Node * root) {
              queue<pair<int,Node*>> q; q.push(make_pair(0,root));
              map<int,Node*> ans;
              for(auto i=q.front();!q.empty();q.pop(),i=q.front()){
                  if(!i.second) continue;
                  ans.insert(i);
                  q.push(make_pair(i.first+1,i.second->right));
                  q.push(make_pair(i.first-1,i.second->left));
              }
              for(auto i:ans) cout<<i.second->data<<" ";
          }
      
      • + 0 comments

        This is the most brilliant solution of this problem.

      • + 0 comments

        Dude you are Genius!!! I struggle to hybrid different Data Structures to come up with such clever solutions, hopefully i could reach that level someday.

      • + 0 comments

        this comment deserves a medal

      • + 0 comments

        how to do for the bottom view. bcz i'm little confused about this code. if pair formed with same value,which one wol be counted? like pair(0,root) and pair(0,root->right->left) which one would print????

      • + 0 comments

        Thanks! I got to learn a lot just by reading this code!

      • + 0 comments

        Legend took me time to get what you did

      • + 0 comments

        Just brilliant! When will I be able to think like this

      • + 0 comments

        Man this solution was genius, took me some time to understand and i tried to solve the problem with this solution and it got the top rank on the leaderboard so if you see me on the leaderboard it is actually this guy!

      • + 0 comments

        Great code! as friends know, insert method when the key is already exists, does not insert and when we start with root, we can be sure that topmost nodes in each horizontal distance are inserted.

      • + 0 comments

        I really can't understand what the code actually does. Can anyone help me out?