Maximum width of an N | Python3 program to implement the above approach ; Function to find the maximum width of . he 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
from collections import deque NEW_LINE def maxWidth ( N , M , cost , s ) : NEW_LINE INDENT adj = [ [ ] for i in range ( N ) ] NEW_LINE for i in range ( M ) : NEW_LINE INDENT adj [ s [ i ] [ 0 ] ] . append ( s [ i ] [ 1 ] ) NEW_LINE DEDENT result = 0 NEW_LINE q = deque ( ) NEW_LINE q . append ( 0 ) NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT count = len ( q ) NEW_LINE result = max ( count , result ) NEW_LINE while ( count > 0 ) : NEW_LINE INDENT temp = q . popleft ( ) NEW_LINE for i in adj [ temp ] : NEW_LINE INDENT q . append ( i ) NEW_LINE DEDENT count -= 1 NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 11 NEW_LINE M = 10 NEW_LINE edges = [ ] NEW_LINE edges . append ( [ 0 , 1 ] ) NEW_LINE edges . append ( [ 0 , 2 ] ) NEW_LINE edges . append ( [ 0 , 3 ] ) NEW_LINE edges . append ( [ 1 , 4 ] ) NEW_LINE edges . append ( [ 1 , 5 ] ) NEW_LINE edges . append ( [ 3 , 6 ] ) NEW_LINE edges . append ( [ 4 , 7 ] ) NEW_LINE edges . append ( [ 6 , 1 ] ) NEW_LINE edges . append ( [ 6 , 8 ] ) NEW_LINE edges . append ( [ 6 , 9 ] ) NEW_LINE cost = [ 1 , 2 , - 1 , 3 , 4 , 5 , 8 , 2 , 6 , 12 , 7 ] NEW_LINE print ( maxWidth ( N , M , cost , edges ) ) NEW_LINE DEDENT