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.
  1. Practice
  2. Data Structures
  3. Trees
  4. Tree : Top View
  5. Discussions

Tree : Top View

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

    • saketbharti20171 + 1 comment

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

      • sarathy_v_krish1 + 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