text: Maximum width of an N | C # 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
code: using System ; using System . Collections . Generic ; class GFG { static int maxWidth ( int N , int M , List < int > cost , List < List < int > > s ) { List < List < int > > adj = new List < List < int > > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { adj . Add ( new List < int > ( ) ) ; } for ( int i = 0 ; i < M ; i ++ ) { adj [ s [ i ] [ 0 ] ] . Add ( s [ i ] [ 1 ] ) ; } int result = 0 ; Queue < int > q = new Queue < int > ( ) ; q . Enqueue ( 0 ) ; while ( q . Count != 0 ) { int count = q . Count ; result = Math . Max ( count , result ) ; while ( count -- > 0 ) { int temp = q . Dequeue ( ) ; for ( int i = 0 ; i < adj [ temp ] . Count ; i ++ ) { q . Enqueue ( adj [ temp ] [ i ] ) ; } } } return result ; } static public void Main ( ) { int N = 11 , M = 10 ; List < List < int > > edges = new List < List < int > > ( ) ; edges . Add ( new List < int > ( ) { 0 , 1 } ) ; edges . Add ( new List < int > ( ) { 0 , 2 } ) ; edges . Add ( new List < int > ( ) { 0 , 3 } ) ; edges . Add ( new List < int > ( ) { 1 , 4 } ) ; edges . Add ( new List < int > ( ) { 1 , 5 } ) ; edges . Add ( new List < int > ( ) { 3 , 6 } ) ; edges . Add ( new List < int > ( ) { 4 , 7 } ) ; edges . Add ( new List < int > ( ) { 6 , 10 } ) ; edges . Add ( new List < int > ( ) { 6 , 8 } ) ; edges . Add ( new List < int > ( ) { 6 , 9 } ) ; List < int > cost = new List < int > ( ) { 1 , 2 , - 1 , 3 , 4 , 5 , 8 , 2 , 6 , 12 , 7 } ; Console . WriteLine ( maxWidth ( N , M , cost , edges ) ) ; } }