CareerCup

balanced max heap will be the answer

sort all the numbers and construct the tree level by level in decreasing order.

Create a binary heap using max heapify, that way all the higher elements will appear in the top levels, causing the tree weight to minimum.

balanced max heap created by those values should be the answer. the heigher value should be at least depth.

Post Order Traversal and calculate the min Weight

public int? GetMinWeight(TreeNode root)
    {
        if (root == null)
            return null;

        int minWeight = int.MaxValue;
        GetMinWeight(root, 1, ref minWeight);
        return minWeight;
    }

    private int GetMinWeight(TreeNode node, int deep, ref int minWeight)
    {
        if (node.Left == null)
            return 0;

        int leftWeight = GetMinWeight(node.Left, deep + 1, ref minWeight);
        int rightWeight = GetMinWeight(node.Right, deep + 1, ref minWeight);
        int weight = node.Value * deep + leftWeight + rightWeight;

        minWeight = Math.Min(minWeight, weight);
        if (node.Left != null)
            minWeight = Math.Min(minWeight, leftWeight);
        if (node.Right != null)
            minWeight = Math.Min(minWeight, rightWeight);

        return weight;
    }
}

I had the same thought that a max heap would provide the minimum answer. After testing it out I realized that there are some heap arrangements that are better than others: e.g. for this list : [1,2,3,8,10,20,43] both these arrangements are heaps:
1. [43, 20, 8, 2, 10, 3, 1] with weight 60
2. [43, 20, 10, 2, 3, 1, 8] with weight 58

So I think the solution is to sort the array in reverse order and treat that as a binary tree (children on node i are 2*i+1 and 2*i+2) .

In Python:

def compute_weight(tree,root,depth):
   if root > len(tree) - 1: 
       return 0
   l = compute_weight(tree, 2*root+1, depth+1)
   r = compute_weight(tree,2*root+2, depth+1)
   return tree[root]*depth + l + r
   
if __name__ == "__main__":
    nums = [60, 10, 43, 8, 5, 20, 3, 2, 2, 1, 1]
    nums.sort() #sort the array
    nums = nums[::-1] #reverse so that that it is sorted max->min
    print compute_weight(nums,0,0)

inki I agree and here is the reason from math stand point of view:
lets take the lets take the "lowest branch of the tree node a and two children b and c. lets say a has depth n then b and c have depth (n + 1) then the weight of this branch is a*n + (b + c)*(n + 1). where a > b and a > c. Now lets swap a and b then
weight of the tree will be b*n + (a + c)*(n + 1) so now lets compare the weights
a * n + (b+c)*(n + 1) and b*n + (a + c)*(n + 1)
opening the brakets from both sides and making all the nessesary manipulations will see that from the left side only b will be left and from the right only a

b > a this means that if highest values need to be at the lowest possible level this can be achieved by constructing max heap from array which is sorted in in descending order.

I don't know much about balanced max heap (I am studying about it now) but here is my attempt at it. I assume that min weight will always be at a node which has 2 leafs under it. If you go any higher - the weight will only increase.

public class SmallestWeightTree {
	private static int height = 0, weight = Integer.MAX_VALUE;
	private static Node nodeMinWeight = null;
	public static int weigh(Node node, int level) {
		int leftWeight = 0, rightWeight = 0, selfWeight = 0, totalWeight = 0;
		if(node.hasLeft()) {
			leftWeight = weigh(node.getLeft(), level + 1);
		} 
		if(node.hasRight()) {
			rightWeight = weigh(node.getRight(), level + 1);
		}
		if(node.isLeaf()) {
			height = height < level ? level : height;
		}
		selfWeight = level * node.getValue();
		totalWeight = leftWeight + rightWeight + selfWeight;
		
		if(level == height - 1) { // At the level right above a leaf, time to compare weights
			if(totalWeight < weight) {
				weight = totalWeight;
				nodeMinWeight = node;
			} 
		}
		return totalWeight;
	}
}

Can someone please explain what a balanced max heap is? Please note I know what a max heap is.