Queries to find the sum of weights of all nodes with vertical width from given range in a Binary Tree | Java 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
import java . io . * ; import java . util . * ; class GFG { static class Node { int data ; Node left ; Node right ; } static Node newNode ( int d ) { Node n = new Node ( ) ; n . data = d ; n . left = null ; n . right = null ; return n ; } static void findwt ( Node root , int wt [ ] , TreeMap < Integer , Integer > um , int width ) { if ( root == null ) { return ; } if ( um . containsKey ( width ) ) { um . put ( width , um . get ( width ) + wt [ root . data ] ) ; } else { um . put ( width , wt [ root . data ] ) ; } findwt ( root . left , wt , um , width - 1 ) ; findwt ( root . right , wt , um , width + 1 ) ; } static void solveQueries ( int wt [ ] , Node root , int [ ] [ ] queries ) { TreeMap < Integer , Integer > um = new TreeMap < Integer , Integer > ( ) ; findwt ( root , wt , um , 0 ) ; int x = 0 ; for ( Map . Entry < Integer , Integer > it : um . entrySet ( ) ) { x += it . getValue ( ) ; um . put ( it . getKey ( ) , x ) ; } for ( int i = 0 ; i < queries . length ; i ++ ) { int l = queries [ i ] [ 0 ] ; int r = queries [ i ] [ 1 ] ; int ans = 0 ; if ( um . containsKey ( r ) ) { ans = um . get ( r ) ; } if ( um . containsKey ( l - 1 ) ) { ans -= um . get ( l - 1 ) ; } System . out . println ( ans ) ; } } public static void main ( String [ ] args ) { 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 } ; int queries [ ] [ ] = { { - 1 , 1 } , { - 2 , - 1 } , { 0 , 3 } } ; solveQueries ( wt , root , queries ) ; } }