xdavidliu 12 months ago+ 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 << ' ';
    }
  }

tech_boy 12 months ago+ 0 comments

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

logbob0401 3 months ago+ 0 comments

[deleted]

venom1724 2 months ago+ 0 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<<" ";
    }