#include <map>
#include <queue>
#include <vector>
using namespace std;
vector<int> verticalOrderTraversal(TreeNode<int>* root) {
vector<int> ans;
if (!root) return ans;
map<int, vector<int>> hnodes;
queue<pair<TreeNode<int>*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto p = q.front();
q.pop();
TreeNode<int>* node = p.first;
int hd = p.second;
hnodes[hd].push_back(node->data);
if (node->left) q.push({node->left, hd-1});
if (node->right) q.push({node->right, hd+1});
}
for (auto it = hnodes.begin(); it != hnodes.end(); it++) {
vector<int>& nodes = it->second;
for (int node_val : nodes) {
ans.push_back(node_val);
}
}
return ans;
}