• + 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 << ' ';
        }
      }