text: Sum of distances of all nodes from a given node | C ++ program for the above approach ; Structure of a binary tree node ; Function that allocates a new node with the given data and NULL to its left and right pointers ; Return newly created 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 ; Stores the sum of distances of all nodes from the given node ; 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; class TreeNode { public : int data , size ; 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 ) { pair < int , int > p = make_pair ( 1 , 0 ) ; if ( root -> left ) { pair < int , int > ptemp = sumofsubtree ( root -> left ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } if ( root -> right ) { pair < int , int > ptemp = sumofsubtree ( root -> right ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } root -> size = p . first ; return p ; } int sum = 0 ; void distance ( TreeNode * root , int target , int distancesum , int n ) { if ( root -> data == target ) { sum = distancesum ; } if ( root -> left ) { int tempsum = distancesum - root -> left -> size + ( n - root -> left -> size ) ; distance ( root -> left , target , tempsum , n ) ; } if ( root -> right ) { int tempsum = distancesum - root -> right -> size + ( n - root -> right -> size ) ; distance ( root -> right , target , tempsum , n ) ; } } 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 target = 3 ; pair < int , int > p = sumofsubtree ( root ) ; int totalnodes = p . first ; distance ( root , target , p . second , totalnodes ) ; cout << sum << endl ; return 0 ; }