Maximum absolute difference between any two level sum in a N | Java program for the above approach ; Function to find the maximum absolute difference of level sum ; Create the adjacency list ; Initialize value of maximum and minimum level sum ; Do Level order traversal keeping track of nodes at every level ; Get the size of queue when the level order traversal for one level finishes ; Iterate for all the nodes in the queue currently ; Dequeue an node from queue ; Enqueue the children of dequeued node ; Update the maximum level sum value ; Update the minimum level sum value ; Return the result ; Driver Code ; Number of nodes and edges ; Edges of the N - ary tree ; Given cost ; Function call
import java . util . * ; class GFG { static void maxAbsDiffLevelSum ( int N , int M , int [ ] cost , int Edges [ ] [ ] ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] adj = new Vector [ N ] ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < M ; i ++ ) { int u = Edges [ i ] [ 0 ] ; int v = Edges [ i ] [ 1 ] ; adj [ u ] . add ( v ) ; } int maxSum = cost [ 0 ] , minSum = cost [ 0 ] ; Queue < Integer > q = new LinkedList < Integer > ( ) ; q . add ( 0 ) ; while ( ! q . isEmpty ( ) ) { int count = q . size ( ) ; int sum = 0 ; while ( count -- > 0 ) { int temp = q . peek ( ) ; q . remove ( ) ; sum = sum + cost [ temp ] ; for ( int i = 0 ; i < adj [ temp ] . size ( ) ; i ++ ) { q . add ( adj [ temp ] . get ( i ) ) ; } } maxSum = Math . max ( sum , maxSum ) ; minSum = Math . min ( sum , minSum ) ; } System . out . print ( Math . abs ( maxSum - minSum ) ) ; } public static void main ( String [ ] args ) { int N = 10 , M = 9 ; int Edges [ ] [ ] = { { 0 , 1 } , { 0 , 2 } , { 0 , 3 } , { 1 , 4 } , { 1 , 5 } , { 3 , 6 } , { 6 , 7 } , { 6 , 8 } , { 6 , 9 } } ; int [ ] cost = { 1 , 2 , - 1 , 3 , 4 , 5 , 8 , 6 , 12 , 7 } ; maxAbsDiffLevelSum ( N , M , cost , Edges ) ; } }