Vertical Sum of a Binary Tree

• Time : $O(n + wlogw)$
• Space : $O(w)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void dfs(TreeNode* node, unordered_map<int,int>& mp, int v) {
    if(!node) return;
    mp[v] += node->val;
    dfs(node->left, mp, v - 1);
    dfs(node->right, mp, v + 1);
}
vector<int> Solution::verticalSum(TreeNode* A) {
    unordered_map<int, int> mp;
    dfs(A,mp,0);
    vector<pair<int, int>> S;
    for(auto [k,v] : mp) S.push_back({k,v});
    sort(begin(S), end(S));
    vector<int> res;
    for(auto [_,v] : S) res.push_back(v);
    return res;
}