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

Tree : Top View

  • dehaka
     + 0 comments

    runs in O(n) time, not O(nlog n), no need to search for horizontal level in a map, the checking is done in constant time with the leftside and rightside vectors

    void topView(Node * root) {
        queue<pair<Node*, int>> levelOrder;
        vector<int> leftside = {root->data};
        vector<int> rightside;
        levelOrder.push({root, 0});
        while (!levelOrder.empty()) {
            Node* temp = levelOrder.front().first;
            int currentHorizontal = levelOrder.front().second;
            if (currentHorizontal <=0 and abs(currentHorizontal) == leftside.size()) {
                leftside.push_back(temp->data);
            } else if (currentHorizontal > 0 and currentHorizontal == rightside.size()+1) {
                rightside.push_back(temp->data);
            }
            if (temp->left != NULL) {
                levelOrder.push({temp->left, currentHorizontal-1});
            }
            if (temp->right != NULL) {
                levelOrder.push({temp->right, currentHorizontal+1});
            }
            levelOrder.pop();
        }
        for (int i=leftside.size()-1; i >= 0; i--) {
            cout << leftside[i] << ' ';
        }
        for (int i=0; i < rightside.size(); i++) {
            cout << rightside[i] << ' ';
        }
    }