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: #include <bits/stdc++.h> NEW_LINE using namespace std ; int maxWidth ( int N , int M , vector < int > cost , vector < vector < int > > s ) { vector < int > adj [ N ] ; for ( int i = 0 ; i < M ; i ++ ) { adj [ s [ i ] [ 0 ] ] . push_back ( s [ i ] [ 1 ] ) ; } int result = 0 ; queue < int > q ; q . push ( 0 ) ; while ( ! q . empty ( ) ) { int count = q . size ( ) ; result = max ( count , result ) ; while ( count -- ) { int temp = q . front ( ) ; q . pop ( ) ; for ( int i = 0 ; i < adj [ temp ] . size ( ) ; i ++ ) { q . push ( adj [ temp ] [ i ] ) ; } } } return result ; } int main ( ) { int N = 11 , M = 10 ; vector < vector < int > > edges ; edges . push_back ( { 0 , 1 } ) ; edges . push_back ( { 0 , 2 } ) ; edges . push_back ( { 0 , 3 } ) ; edges . push_back ( { 1 , 4 } ) ; edges . push_back ( { 1 , 5 } ) ; edges . push_back ( { 3 , 6 } ) ; edges . push_back ( { 4 , 7 } ) ; edges . push_back ( { 6 , 10 } ) ; edges . push_back ( { 6 , 8 } ) ; edges . push_back ( { 6 , 9 } ) ; vector < int > cost = { 1 , 2 , -1 , 3 , 4 , 5 , 8 , 2 , 6 , 12 , 7 } ; cout << maxWidth ( N , M , cost , edges ) ; return 0 ; }