Sum of distances of all nodes from a given node | ''Stores the sum of distances of all nodes from the given node ; ''Structure of a binary tree node ; ''Function to count the number of nodes in the left and right subtrees ; '' Initialize a pair that stores  the pair {number of nodes, depth} ; '' Finding the number of nodes  in the left subtree ; '' Find the number of nodes  in the right subtree ; '' Filling up size field ; ''Function to find the total distance ; '' If target node matches with  the current node ; '' If root.left is not null ; '' Update sum ; '' Recur for the left subtree ; '' If root.right is not null ; '' Apply the formula given  in the approach ; '' Recur for the right subtree ; ''Driver Code ; '' Input tree ; '' Total number of nodes ; '' Print the sum of distances
sum = 0 NEW_LINE class TreeNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . size = 0 NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def sumofsubtree ( root ) : NEW_LINE INDENT p = [ 1 , 0 ] NEW_LINE if ( root . left ) : 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 ) : NEW_LINE INDENT ptemp = sumofsubtree ( root . right ) NEW_LINE p [ 1 ] += ptemp [ 0 ] + ptemp [ 1 ] NEW_LINE p [ 0 ] += ptemp [ 0 ] NEW_LINE DEDENT root . size = p [ 0 ] NEW_LINE return p NEW_LINE DEDENT def distance ( root , target , distancesum , n ) : NEW_LINE INDENT global sum NEW_LINE if ( root . data == target ) : NEW_LINE INDENT sum = distancesum NEW_LINE DEDENT if ( root . left ) : NEW_LINE INDENT tempsum = ( distancesum - root . left . size + ( n - root . left . size ) ) NEW_LINE distance ( root . left , target , tempsum , n ) NEW_LINE DEDENT if ( root . right ) : NEW_LINE INDENT tempsum = ( distancesum - root . right . size + ( n - root . right . size ) ) NEW_LINE distance ( root . right , target , tempsum , n ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = TreeNode ( 1 ) NEW_LINE root . left = TreeNode ( 2 ) NEW_LINE root . right = TreeNode ( 3 ) NEW_LINE root . left . left = TreeNode ( 4 ) NEW_LINE root . left . right = TreeNode ( 5 ) NEW_LINE root . right . left = TreeNode ( 6 ) NEW_LINE root . right . right = TreeNode ( 7 ) NEW_LINE root . left . left . left = TreeNode ( 8 ) NEW_LINE root . left . left . right = TreeNode ( 9 ) NEW_LINE target = 3 NEW_LINE p = sumofsubtree ( root ) NEW_LINE totalnodes = p [ 0 ] NEW_LINE distance ( root , target , p [ 1 ] , totalnodes ) NEW_LINE print ( sum ) NEW_LINE DEDENT