Sum of subtree depths for every node of a given Binary Tree | Binary tree node ; Constructor to set the data of the newly created tree node ; Function to allocate a new node with the given data and null in its left and right pointers ; DFS function to calculate the sum of depths of all subtrees depth sum ; Store total number of node in its subtree and total sum of depth in its subtree ; Check if left is not null ; Call recursively the DFS function for left child ; Increment the sum of depths by ptemp . first + p . temp . first ; Increment p . first by count of noded in left subtree ; Check if right is not null ; Call recursively the DFS function for right child ; Increment the sum of depths by ptemp . first + p . temp . first ; Increment p . first by count of nodes in right subtree ; Increment the result by total sum of depth in current subtree ; Return p ; Given Tree ; Print the result
class TreeNode : 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 ans = 0 NEW_LINE def newNode ( data ) : NEW_LINE INDENT Node = TreeNode ( data ) NEW_LINE return ( Node ) NEW_LINE DEDENT def sumofsubtree ( root ) : NEW_LINE INDENT global ans NEW_LINE p = [ 1 , 0 ] NEW_LINE if ( root . left != None ) : NEW_LINE INDENT ptemp = sumofsubtree ( root . left ) NEW_LINE p [ 1 ] += ptemp [ 0 ] + ptemp [ 1 ] NEW_LINE p [ 0 ] += ptemp [ 0 ] NEW_LINE DEDENT if ( root . right != None ) : NEW_LINE INDENT ptemp = sumofsubtree ( root . right ) NEW_LINE p [ 1 ] += ptemp [ 0 ] + ptemp [ 1 ] NEW_LINE p [ 0 ] += ptemp [ 0 ] NEW_LINE DEDENT ans += p [ 1 ] NEW_LINE return p NEW_LINE DEDENT 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 . left . right = newNode ( 5 ) NEW_LINE root . right . left = newNode ( 6 ) NEW_LINE root . right . right = newNode ( 7 ) NEW_LINE root . left . left . left = newNode ( 8 ) NEW_LINE root . left . left . right = newNode ( 9 ) NEW_LINE sumofsubtree ( root ) NEW_LINE print ( ans ) NEW_LINE