Difference between sums of odd level and even level nodes of a Binary Tree | Helper function that allocates a new node with the given data and None left and right poers . ; Construct to create a new node ; return difference of sums of odd level and even level ; create a queue for level order traversal ; traverse until the queue is empty ; traverse for complete level ; check if level no . is even or odd and accordingly update the evenSum or oddSum ; check for left child ; check for right child ; Driver Code ; Let us create Binary Tree shown in above example
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def evenOddLevelDifference ( root ) : NEW_LINE INDENT if ( not root ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT q = [ ] NEW_LINE q . append ( root ) NEW_LINE level = 0 NEW_LINE evenSum = 0 NEW_LINE oddSum = 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 ( level % 2 == 0 ) : NEW_LINE INDENT evenSum += temp . data NEW_LINE DEDENT else : NEW_LINE INDENT oddSum += temp . data 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 ( oddSum - evenSum ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 5 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 6 ) NEW_LINE root . left . left = newNode ( 1 ) NEW_LINE root . left . right = newNode ( 4 ) NEW_LINE root . left . right . left = newNode ( 3 ) NEW_LINE root . right . right = newNode ( 8 ) NEW_LINE root . right . right . right = newNode ( 9 ) NEW_LINE root . right . right . left = newNode ( 7 ) NEW_LINE result = evenOddLevelDifference ( root ) NEW_LINE print ( " Diffence ▁ between ▁ sums ▁ is " , result ) NEW_LINE DEDENT