Find the Level of a Binary Tree with Width K | Python3 program to implement the above approach ; Structure of a Tree node ; Function to create new node ; Function returns required level of width k , if found else - 1 ; To store the node and the label and perform traversal ; Taking the last label of each level of the tree ; Check width of current level ; If the width is equal to k then return that level ; Taking the first label of each level of the tree ; If any level does not has width equal to k , return - 1 ; Driver Code
from collections import deque NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def findLevel ( root : Node , k : int , level : int ) -> int : NEW_LINE INDENT qt = deque ( ) NEW_LINE qt . append ( [ root , 0 ] ) NEW_LINE count = 1 NEW_LINE b = 0 NEW_LINE a = 0 NEW_LINE while qt : NEW_LINE INDENT temp = qt . popleft ( ) NEW_LINE if ( count == 1 ) : NEW_LINE INDENT b = temp [ 1 ] NEW_LINE DEDENT if ( temp [ 0 ] . left ) : NEW_LINE INDENT qt . append ( [ temp [ 0 ] . left , 2 * temp [ 1 ] ] ) NEW_LINE DEDENT if ( temp [ 0 ] . right ) : NEW_LINE INDENT qt . append ( [ temp [ 0 ] . right , 2 * temp [ 1 ] + 1 ] ) NEW_LINE DEDENT count -= 1 NEW_LINE if ( count == 0 ) : NEW_LINE INDENT if ( b - a + 1 == k ) : NEW_LINE INDENT return level NEW_LINE DEDENT secondLabel = qt [ 0 ] NEW_LINE a = secondLabel [ 1 ] NEW_LINE level += 1 NEW_LINE count = len ( qt ) NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = Node ( 5 ) NEW_LINE root . left = Node ( 6 ) NEW_LINE root . right = Node ( 2 ) NEW_LINE root . right . right = Node ( 8 ) NEW_LINE root . left . left = Node ( 7 ) NEW_LINE root . left . left . left = Node ( 5 ) NEW_LINE root . left . right = Node ( 3 ) NEW_LINE root . left . right . right = Node ( 4 ) NEW_LINE k = 4 NEW_LINE print ( findLevel ( root , k , 1 ) ) NEW_LINE DEDENT