/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone{
	public static class Node{
		Node left, right;
		int data;
		Node(int data, Node left, Node right){
			this.data = data;
			this.left = left;
			this.right = right;
		}
		Node(int data){
			this(data, null, null);
		}
	}
	
	public static int depthSum(Node root) {
	    Queue<Node> q = new LinkedList<Node>();
	    q.add(root);
	    int siblings = 1;
	    int totalSum = 0, levelSum = 0, level = 0;
	
	    while(!q.isEmpty()) {
	        Node n = q.remove();
	        levelSum += n.data;
	
	        if(n.left != null)                     // Add left child 
	            q.add(n.left);
	
	        if(n.right != null)                    // Add right child
	            q.add(n.right);
	
	        if(--siblings == 0){                   // All siblings have been probed
	            siblings = q.size();               // Children become siblings
	            totalSum += levelSum * level;      // increment totalSum
	            level++;                           // increment level
	            levelSum = 0;                      // reinitialize levelSum
	        }
	    }
	
	    return totalSum;
	}
	
	public static void main (String[] args) throws java.lang.Exception{
		Node root = new Node(1,
						new Node(2,
							null,
							new Node(5)
						), 
						new Node(3,
							new Node(6),
							new Node(7)
						)
					);
		System.out.println("Expected Answer : (1)*0 + (2 + 3)*1 + (5 + 6 + 7)*2 = 41");
		System.out.println("Actual Answer   : " + depthSum(root));
	}
}