# 2 C++ Solution with hashmap and 2 vectors respectively

• C++ people please do realize that maps are implemented as binary search trees (Red-Black Tree) while unordered_maps are implemented as hash table. This library implementation detail would cause significant difference in running time, since we all know that search, removal, and insertion operations on BST have logarithmic complexity while those operations on hash table have average constant-time complexity.

``````public:
vector<vector<int>> verticalOrder(TreeNode* root) {
if (!root) return vector<vector<int>> ();
/**
* sol1: using level-traversal with two vectors storing elements which their column is less
* than and equal to/greater than root, respectively.
* By using level-traversal, it can promise the order in each column is from top to bottom
*
* Time O(N), Space O(N).
**/
vector<vector<int>> pos; // store those elements which their column are as root or on the right of root
vector<vector<int>> neg; // store those elements which their column are on the left of root
queue<pair<TreeNode*, int>> nodeQ;
nodeQ.push(make_pair(root, 0));
while (!nodeQ.empty()) {
pair<TreeNode*, int> node = nodeQ.front();
nodeQ.pop();
pushToVec(pos, neg, node.first, node.second);
if (node.first->left)
nodeQ.push(make_pair(node.first->left, node.second-1));
if (node.first->right)
nodeQ.push(make_pair(node.first->right, node.second+1));
}
reverse(neg.begin(), neg.end());
neg.insert(neg.end(), pos.begin(), pos.end());
return neg;

/**
* sol2: using level-traversal with hash table
* Time O(N), Space O(N)
**/
vector<vector<int>> res;
int minCol = INT_MAX, maxCol = INT_MIN;
unordered_map<int, vector<int>> cols;
queue<pair<TreeNode*, int>> nodeQ;
nodeQ.push(make_pair(root, 0));
while (!nodeQ.empty()) {
pair<TreeNode*, int> node = nodeQ.front();
nodeQ.pop();
cols[node.second].push_back(node.first->val);
minCol = min(minCol, node.second);
maxCol = max(maxCol, node.second);
if (node.first->left)
nodeQ.push(make_pair(node.first->left, node.second-1));
if (node.first->right)
nodeQ.push(make_pair(node.first->right, node.second+1));
}

for (int i=minCol; i<=maxCol; i++)
res.push_back(cols[i]);

return res;
}

private:
void pushToVec(vector<vector<int>>& pos, vector<vector<int>>& neg, TreeNode* root, int curRange) {
if (curRange>=0) {
if (pos.size()<curRange+1)
pos.push_back(vector<int>());
pos[curRange].push_back(root->val);
} else {
if (neg.size()<-curRange)
neg.push_back(vector<int>());
neg[-curRange-1].push_back(root->val);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.