Sum of specially balanced nodes from a given Binary Tree | Structure of Binary Tree ; Function to create a new node ; Return the created node ; Function to insert a node in the tree ; Left insertion ; Right insertion ; Return the root node ; Function to find sum of specially balanced nodes in the Tree ; Base Case ; Find the left subtree sum ; Find the right subtree sum ; Condition of specially balanced node ; Condition of specially balanced node ; Return the sum ; Function to build the binary tree ; Form root node of the tree ; Insert nodes into tree ; Create a new Node ; Insert the node ; Return the root of the Tree ; Function to find the sum of specially balanced nodes ; Build Tree ; Stores the sum of specially balanced node ; Function Call ; Print required sum ; Driver code ; Given nodes ; Given root ; Given path info of nodes from root ; Given node values ; Function Call
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newnode ( data ) : NEW_LINE INDENT temp = Node ( data ) NEW_LINE return temp NEW_LINE DEDENT def insert ( s , i , N , root , temp ) : NEW_LINE INDENT if ( i == N ) : NEW_LINE INDENT return temp NEW_LINE DEDENT if ( s [ i ] == ' L ' ) : NEW_LINE INDENT root . left = insert ( s , i + 1 , N , root . left , temp ) NEW_LINE DEDENT else : NEW_LINE INDENT root . right = insert ( s , i + 1 , N , root . right , temp ) NEW_LINE DEDENT return root NEW_LINE DEDENT def SBTUtil ( root , sum ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return [ 0 , sum ] NEW_LINE DEDENT if ( root . left == None and root . right == None ) : NEW_LINE INDENT return [ root . data , sum ] NEW_LINE DEDENT left , sum = SBTUtil ( root . left , sum ) NEW_LINE right , sum = SBTUtil ( root . right , sum ) NEW_LINE if ( root . left and root . right ) : NEW_LINE INDENT if ( ( left % 2 == 0 and right % 2 != 0 ) or ( left % 2 != 0 and right % 2 == 0 ) ) : NEW_LINE INDENT sum += root . data NEW_LINE DEDENT DEDENT return [ left + right + root . data , sum ] NEW_LINE DEDENT def build_tree ( R , N , str , values ) : NEW_LINE INDENT root = newnode ( R ) NEW_LINE for i in range ( 0 , N - 1 ) : NEW_LINE INDENT s = str [ i ] NEW_LINE x = values [ i ] NEW_LINE temp = newnode ( x ) NEW_LINE root = insert ( s , 0 , len ( s ) , root , temp ) NEW_LINE DEDENT return root NEW_LINE DEDENT def speciallyBalancedNodes ( R , N , str , values ) : NEW_LINE INDENT root = build_tree ( R , N , str , values ) NEW_LINE sum = 0 NEW_LINE tmp , sum = SBTUtil ( root , sum ) NEW_LINE print ( sum , end = ' ▁ ' ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 7 NEW_LINE R = 12 NEW_LINE str = [ " L " , " R " , " RL " , " RR " , " RLL " , " RLR " ] NEW_LINE values = [ 17 , 16 , 4 , 9 , 2 , 3 ] NEW_LINE speciallyBalancedNodes ( R , N , str , values ) NEW_LINE DEDENT