Sum of distances of all nodes from a given node | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static class TreeNode { int data , size ; TreeNode left ; TreeNode right ; } ; static TreeNode newNode ( int data ) { TreeNode Node = new TreeNode ( ) ; Node . data = data ; Node . left = null ; Node . right = null ; return ( Node ) ; } static pair sumofsubtree ( TreeNode root ) { pair p = new pair ( 1 , 0 ) ; if ( root . left != null ) { pair ptemp = sumofsubtree ( root . left ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } if ( root . right != null ) { pair ptemp = sumofsubtree ( root . right ) ; p . second += ptemp . first + ptemp . second ; p . first += ptemp . first ; } root . size = p . first ; return p ; } static int sum = 0 ; static void distance ( TreeNode root , int target , int distancesum , int n ) { if ( root . data == target ) { sum = distancesum ; } if ( root . left != null ) { int tempsum = distancesum - root . left . size + ( n - root . left . size ) ; distance ( root . left , target , tempsum , n ) ; } if ( root . right != null ) { int tempsum = distancesum - root . right . size + ( n - root . right . size ) ; distance ( root . right , target , tempsum , n ) ; } } public static void main ( String [ ] args ) { 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 p = sumofsubtree ( root ) ; int totalnodes = p . first ; distance ( root , target , p . second , totalnodes ) ; System . out . print ( sum + "NEW_LINE"); } }