Find depth of the deepest odd level leaf node | Python3 program to find depth of the deepest odd level leaf node of binary tree ; tree node returns a new tree Node ; return max odd number depth of leaf node ; create a queue for level order traversal ; traverse until the queue is empty ; traverse for complete level ; check if the node is leaf node and level is odd if level is odd , then update result ; check for left child ; check for right child ; Driver Code ; construct a tree
INT_MAX = 2 ** 31 NEW_LINE class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def maxOddLevelDepth ( root ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT q = [ ] NEW_LINE q . append ( root ) NEW_LINE result = INT_MAX NEW_LINE level = 0 NEW_LINE while ( len ( q ) ) : NEW_LINE INDENT size = len ( q ) NEW_LINE level += 1 NEW_LINE while ( size > 0 ) : NEW_LINE INDENT temp = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE if ( not temp . left and not temp . right and ( level % 2 != 0 ) ) : NEW_LINE INDENT result = level NEW_LINE DEDENT if ( temp . left ) : NEW_LINE INDENT q . append ( temp . left ) NEW_LINE DEDENT if ( temp . right ) : NEW_LINE INDENT q . append ( temp . right ) NEW_LINE DEDENT size -= 1 NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . left = newNode ( 4 ) NEW_LINE root . right . left = newNode ( 5 ) NEW_LINE root . right . right = newNode ( 6 ) NEW_LINE root . right . left . right = newNode ( 7 ) NEW_LINE root . right . right . right = newNode ( 8 ) NEW_LINE root . right . left . right . left = newNode ( 9 ) NEW_LINE root . right . right . right . right = newNode ( 10 ) NEW_LINE root . right . right . right . right . left = newNode ( 11 ) NEW_LINE result = maxOddLevelDepth ( root ) NEW_LINE if ( result == INT_MAX ) : NEW_LINE INDENT print ( " No ▁ leaf ▁ node ▁ at ▁ odd ▁ level " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( result , end = " " ) NEW_LINE print ( " ▁ is ▁ the ▁ required ▁ depth ▁ " ) NEW_LINE DEDENT DEDENT