Queries to find the sum of weights of all nodes with vertical width from given range in a Binary Tree | C ++ program for the above approach ; Structure of a node ; Function to create new node ; Function to pre - compute the sum of weights at each width position ; Base Case ; Update the current width position weight ; Recursive Call to its left ; Recursive Call to its right ; Function to find the sum of the weights of nodes whose vertical widths lies over the range [ L , R ] for Q queries ; Stores the weight sum of each width position ; Function Call to fill um ; Stores the sum of all previous nodes , while traversing Map ; Traverse the Map um ; Iterate over all queries ; Print the result for the current query [ l , r ] ; Driver Code ; Given Tree
#include <bits/stdc++.h> NEW_LINE 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 < int , int > & 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 < vector < int > > queries ) { map < int , int > 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 << um [ r ] - um [ l - 1 ] << " STRNEWLINE " ; } } int main ( ) { int N = 8 ; Node * root = newNode ( 1 ) ; root -> left = newNode ( 3 ) ; root -> 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 < vector < int > > queries { { -1 , 1 } , { -2 , -1 } , { 0 , 3 } } ; solveQueries ( wt , root , queries ) ; return 0 ; }