#include <bits/stdc++.h>
/************************************************************
Following is the Binary Tree node class
template <typename T = int>
class TreeNode
{
public:
T data;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(T val)
{
this->data = val;
left = NULL;
right = NULL;
}
~TreeNode()
{
if (left != NULL)
{
delete left;
}
if (right != NULL)
{
delete right;
}
}
};
************************************************************/
#include <map> //MYSOL WITH HNODE from AI
#include <queue>
#include <vector>
using namespace std;
void traverse(TreeNode<int>* root, int parh, map<TreeNode<int>*, int>& hord) { //get the horizontal distance array
if (root) {
hord[root] = parh;
traverse(root->left, parh - 1, hord);
traverse(root->right, parh + 1, hord);
}
}
vector<int> verticalOrderTraversal(TreeNode<int>* root) {
map<TreeNode<int>*, int> hord; //(node-horizontal distance)
traverse(root, 0, hord);
vector<int> ans;
/* creating the map of vector which will contain all nodes at
horizontal distance */
map<int, vector<int>> hnodes;
for (auto it = hord.begin(); it != hord.end(); it++) {
hnodes[it->second].push_back(it->first->data);
}
// now hnodes has att the nodes mapped with horizontal distance (horizontal distance-node)
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;
}