Maximum width of an N | Java program to implement the above approach ; Function to find the maximum width of the tree using level order traversal ; Store the edges of the tree ; Stores maximum width of the tree ; Stores the nodes of each level ; Insert root node ; Perform level order traversal on the tree ; Stores the size of the queue ; Update maximum width ; Push the nodes of the next level and pop the elements of the current level ; Get element from the front the Queue ; Push all nodes of the next level . ; Return the result . ; Driver Code ; Constructed tree is : 1 / | \ 2 - 1 3 / \ \ 4 5 8 / / | \ 2 6 12 7
import java . io . * ; import java . util . * ; class GFG { static int maxWidth ( int N , int M , ArrayList < Integer > cost , ArrayList < ArrayList < Integer > > s ) { ArrayList < ArrayList < Integer > > adj = new ArrayList < ArrayList < Integer > > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { adj . add ( new ArrayList < Integer > ( ) ) ; } for ( int i = 0 ; i < M ; i ++ ) { adj . get ( s . get ( i ) . get ( 0 ) ) . add ( s . get ( i ) . get ( 1 ) ) ; } int result = 0 ; Queue < Integer > q = new LinkedList < > ( ) ; q . add ( 0 ) ; while ( q . size ( ) != 0 ) { int count = q . size ( ) ; result = Math . max ( count , result ) ; while ( count -- > 0 ) { int temp = q . remove ( ) ; for ( int i = 0 ; i < adj . get ( temp ) . size ( ) ; i ++ ) { q . add ( adj . get ( temp ) . get ( i ) ) ; } } } return result ; } public static void main ( String [ ] args ) { int N = 11 , M = 10 ; ArrayList < ArrayList < Integer > > edges = new ArrayList < ArrayList < Integer > > ( ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 0 , 1 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 0 , 2 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 0 , 3 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 4 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 1 , 5 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 3 , 6 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 4 , 7 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 10 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 8 ) ) ) ; edges . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 9 ) ) ) ; ArrayList < Integer > cost = new ArrayList < Integer > ( Arrays . asList ( 1 , 2 , - 1 , 3 , 4 , 5 , 8 , 2 , 6 , 12 , 7 ) ) ; System . out . println ( maxWidth ( N , M , cost , edges ) ) ; } }