Sum of distances of all nodes from a given node | Javascript 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 ; 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 ; Input tree ; Total number of nodes ; Print the sum of distances
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } class Node { constructor ( data ) { this . data = data ; this . size = 0 ; this . left = this . right = null ; } } function sumofsubtree ( root ) { let p = new pair ( 1 , 0 ) ; if ( root . left != null ) { let ptemp = sumofsubtree ( root . left ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } if ( root . right != null ) { let ptemp = sumofsubtree ( root . right ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } root . size = p . first ; return p ; } let sum = 0 ; function distance ( root , target , distancesum , n ) { if ( root . data == target ) { sum = distancesum ; } if ( root . left != null ) { let tempsum = distancesum - root . left . size + ( n - root . left . size ) ; distance ( root . left , target , tempsum , n ) ; } if ( root . right != null ) { let tempsum = distancesum - root . right . size + ( n - root . right . size ) ; distance ( root . right , target , tempsum , n ) ; } } let root = new Node ( 1 ) ; root . left = new Node ( 2 ) ; root . right = new Node ( 3 ) ; root . left . left = new Node ( 4 ) ; root . left . right = new Node ( 5 ) ; root . right . left = new Node ( 6 ) ; root . right . right = new Node ( 7 ) ; root . left . left . left = new Node ( 8 ) ; root . left . left . right = new Node ( 9 ) ; let target = 3 ; let p = sumofsubtree ( root ) ; let totalnodes = p . first ; distance ( root , target , p . second , totalnodes ) ; document . write ( sum + " " ) ;