# Queries to find the sum of weights of all nodes with vertical width from given range in a Binary Tree

#include using namespace std; struct Node { int data; Node* left; Node* right;}; Node* newNode(int d){ Node* n = new Node; n->data = d; n->left = NULL; n->right = NULL; return n;} void findwt(Node* root, int wt[], map& um, int width = 0){ if (root == NULL) { return; } um[width] += wt[root->data]; findwt(root->left, wt, um, width – 1); findwt(root->right, wt, um, width + 1);} void solveQueries(int wt[], Node* root, vector queries){ map um; findwt(root, wt, um); int x = 0; for (auto it = um.begin(); it != um.end(); it++) { x += it->second; um[it->first] = x; } for (int i = 0; i < queries.size(); i++) { int l = queries[i][0]; int r = queries[i][1]; cout left->left = newNode(5); root->left->right = newNode(6); root->right = newNode(2); root->right->right = newNode(4); root->right->right->left = newNode(7); root->right->right->right = newNode(0); int wt[] = { 8, 6, 4, 5, 1, 2, 9, 1 }; vector queries{ { -1, 1 }, { -2, -1 }, { 0, 3 } }; solveQueries(wt, root, queries); return 0;}