Sum of subtree depths for every node of a given Binary Tree | C ++ program for the above approach ; Binary 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 ; Driver Code ; Given Tree ; Print the result
#include <bits/stdc++.h> NEW_LINE using namespace std ; class TreeNode { public : int data ; TreeNode * left ; TreeNode * right ; } ; TreeNode * newNode ( int data ) { TreeNode * Node = new TreeNode ( ) ; Node -> data = data ; Node -> left = NULL ; Node -> right = NULL ; return ( Node ) ; } pair < int , int > sumofsubtree ( TreeNode * root , int & ans ) { pair < int , int > p = make_pair ( 1 , 0 ) ; if ( root -> left ) { pair < int , int > ptemp = sumofsubtree ( root -> left , ans ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } if ( root -> right ) { pair < int , int > ptemp = sumofsubtree ( root -> right , ans ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } ans += p . second ; return p ; } int main ( ) { TreeNode * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 7 ) ; root -> left -> left -> left = newNode ( 8 ) ; root -> left -> left -> right = newNode ( 9 ) ; int ans = 0 ; sumofsubtree ( root , ans ) ; cout << ans ; return 0 ; }