CareerCup

Here is what i can think of, let me know if you replied differently.
sort the data provided as input , and start inserting the data in binary tree from heightest input value so that all top values will be at low level and low values of input will be at high level. Insertion in tree should be done by traversing the tree in level order and left tree should be inserted before right tree. Total time to sort the input data O(nlogn)+building tree[O(n)]+calculating weight[O(n)]= Total TimeComplexity[O(nlogn)] ..

why are we even constructing the final tree. the question is to only calculate the minimum tree weight..
just sort the array and dot multiply with
a[]={1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,.....}-> n length

example 4,5,6
sorted 6,5,4
answer= 6*1+5*2+4*2 = 24

Why don't build binary tree (where top is max element) - in that case the further element from the root (greater level) - the smaller it's value - this should give minimum sum.

As this is binary tree, so we have to sort array in descending order and treat this array like we have stored max-heap. So this will be complete binary tree which is left aligned.
Then calculate tree weight.

It is simple

why not just create a max heap out of the array of element. Creating a max heap can be done in o(n) if it is balanced!

Let's consider the input is sorted in descending order.
10,9,8,7,6,5,4,3,2,1
Obviously for problem definition of the binary tree weight to have the minimal weight the "heavy" elements must be placed close to the root.
This means, that in our case root node holds 10, it's children hold 9 and 8, their children hold 7,6 and 5,4 respectively. And so on.
So we have the heap. If you want to present it not as an array, but as a tree you have to “translate” indexes to left/right pointers.

//one based calculations
getLeft(vector<int> input, int parent) {
if (parent*2 <= input.length())
return parent*2;
return -1;
}

Simular getRight(…)

Even better one can write a function getParent()

If the input is not sorted, sort it first.

In other words the time complexity of building the tree is 0 if the input is sorted and O(n*log(n)) if not.

O(n) Solution

The straight forward way to solve this problem is to sort the array and then calculate the tree weight. This has a complexity of O(n*log(n)). However we don't need to fully sort the array to produce a minimum weight tree. There are many other orderings that work because the order within each level does not matter. So there should be a way to solve the problem faster than fully sorting the array and perhaps even a way with less complexity than O(n*log(n)). And guess what, there is.

The basic idea is to find the 1st, 3rd, 7th, 15th, ... (n/2-1)th largest values in the array and then partition the array about those values. To do that we partition the array around its (n/2-1)th largest value, then recursively partition the left side about its (n/2-1)th largest value until no more partitions are possible. We use the selection algo to do each partition, but in this case, we don't care about the normal output of the selection algo: the kth largest element. Rather we care about the side effect of what it does to the input array, i.e. partitioning the array about its (n/2-1)th largest value. The end effect of this partitioning is a binary tree with minimum weight.

The selection algo has an average complexity of O(n) and it will be run log(n) times, but each time it is run n shrinks by a factor of 2 (n + n/2 + n/4 + n/8 ... = 2n), thus the overall complexity is O(n). CAVEAT: the worst case performance remains O(n^2) and depends on the choice of pivots.

int findMinimumWeight(int a[]) {
		optimize(a);
		return calculateWeight(a);
	}
	
	int calculateWeight(int a[]) {
		int weight = 0;
		int level = 0;
		int nextLevel = 1;
		for (int i = 0; i < a.length; i++) {
			if (i == nextLevel) {
				++level;
				nextLevel = (1 << level) - 1;
			}
			weight += a[i]*(level+1);
		}
		return weight;		
	}
	
	int[] optimize(int a[]) {
		iterations = 0;
		for (int k = a.length; k > 1; k /= 2) {
			selectLargest(a, 0, k-1, k / 2 + 1);
		}		
		System.out.println("n= " + a.length + " iterations=" + iterations + " efficiency=" + ((float)iterations / a.length) + " log(n)=" + Math.log(a.length));
		return a;
	}
	
	// Selects the kth largest value from the array.
	// As a side effect, it partitions the array around the kth largest value.
	// O(n)
	int selectLargest(int a[], int i, int j, int k) {
		//System.out.println(i + "," + j + "," + k);
		++iterations;
		if (i == j) {
			return k == 1 ? a[i] : -1;
		}
		int pivot = a[i + (j - i) / 2];
		int pivotIndex = partition(a, i, j, pivot);
		int kprime = pivotIndex - i + 1;
		if (kprime == k) {
			return pivot;
		}
		if (kprime < k) {
			return selectLargest(a, pivotIndex + 1, j, k - kprime);
		}
		else {
			return selectLargest(a, i, pivotIndex - 1, k);
		}
	}
	
	int partition(int a[], int i, int j, int pivot) {
		int k = i;
		while (k <= j) {
			++iterations;
			if (a[k] == pivot) {
				++k;
			}
			else if (a[k] > pivot) {
				swap(a, i, k);
				++i;
				++k;
			}
			else {
				swap(a, k, j);
				--j;
			}
		}
		return k - 1;
	}
	
	void swap(int a[], int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

if we sort the array and make a balance binary tree then it give the minimum weight binary tree

// LearnApplication.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Stack.cpp"
#include <hash_map>
#include <string>
#include <iostream>
#include <hash_map>
#include <stdio.h>
#include <sstream>

void merge(int*,int*,int,int,int);
void mergeSort(int* a, int* b, int low, int high){
int pivot;
if (low<high){
pivot=(low+high)/2;
mergeSort(a,b,low,pivot);
mergeSort(a,b,pivot+1,high);
merge(a,b,low,pivot,high);
}
}
void merge(int* a, int* b, int low, int pivot, int high){
int h,i,j,k;
h=i=low;
j=pivot+1;
while(h<=pivot && j<=high){
if (a[h]>=a[j]){
b[i]=a[h];
h++;
}else{
b[i]=a[j];
j++;
}
i++;
}
if(h>pivot)
{
for(k=j; k<=high; k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h; k<=pivot; k++)
{
b[i]=a[k];
i++;
}
}
for(k=low; k<=high; k++) a[k]=b[k];

}
typedef struct node
{
struct node*left;
struct node*right;
char data;
}node;

node* createFromArray(int c[],int n){
node* tree=NULL;
if (c[n]!='\0'){
tree=(node*)malloc(sizeof(node));
tree->left=createFromArray(c,2*n+1);
tree->data=c[n];
tree->right=createFromArray(c,2*n+2);
}
return tree;
}
void parseInOrder(node* tree){
while(tree!=NULL){
parseInOrder(tree->left);
printf("%d \t",tree->data);
parseInOrder(tree->right);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int c_array[]={12,31,5,12,65,23,21,43};
int num;
num = sizeof(c_array)/sizeof(int);
int b[8]={0};
mergeSort(c_array,b,0,num-1);
node *tree;
tree=createFromArray(c_array,0);
parseInOrder(tree);
}

public void subTreeLevelSum(List<Integer> item) {
		if (root == null) {
			return;
		}
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		sumSubTreeWithLevel(root, item, 1, map);
		Set<Integer> set = map.keySet();
		int min = Integer.MAX_VALUE;
		int givenkey = Integer.MAX_VALUE;
		for (Integer key : set) {
			int sum = map.get(key);
			if (sum < min) {
				givenkey = key;
				min = sum;
			}
		}
		System.out.println("Minimum Sum : " + min + " with a given key : " + givenkey);
	}
	
	private void sumSubTreeWithLevel(TreeNode node, List<Integer> items, int level, Map<Integer, Integer> map) {
		if (node == null) {
			return;
		}
		if (items.contains(node.data)) {
			int sum = sumUpTheBinaryTree(level, node);
			map.put(node.data, sum);
		}
		sumSubTreeWithLevel(node.left, items, level + 1, map);
		sumSubTreeWithLevel(node.right, items, level + 1, map);
	}
	
	private int sumUpTheBinaryTree(int level, TreeNode node) {
		if (node == null) {
			return 0; 
		}
		int sum1 = sumUpTheBinaryTree(level + 1, node.left);
		int sum2 = sumUpTheBinaryTree(level + 1, node.right);
		int result = node.data * level + sum1  + sum2;
		return (result);
	}

INPUT: 
		TreePath t = new TreePath();
		t.insert(4);
		t.insert(2);
		t.insert(3);
		t.insert(1);
		t.insert(6);
		t.insert(5);
		t.insert(7);
//		t.postorder();
		List<Integer> items = new ArrayList<Integer>();
		items.add(6);
		items.add(2);
t.subTreeLevelSum(items);

OUTPUT:
-------------
Minimum Sum : 16 with a given key : 2

awesome answer.

This is a wrong solution. If you put the top most value in the low level then all the other values would be in the left of it which would increase the depth of the tree.
I think the right solution is first sort the tree and then put the median on the root and recursively process the left and the right of the tree

Complete wrong.

First, Sort the given data.O(nlogn) time.
Second, take the middle value of the sorted data and Make middle value as root node of binary tree.If total number of data is even, then take middle value from (middle +1) position.Now Insert values in binary tree from middle value to least less value (middle to left side) and later insert values in binary tree from highest value to the middle value (right to middle side).

Can you tell is this tree a BST?

@prabal77

What was your answer?

Can anybody post the pseudo code of the implementation of the above problem

I am stuck with another problem. can anybody help me? the link to the problem is commissies.ch.tudelft.nl/chipcie/archief/1999/ekp/html/proba.html

What about to sort elements in decreasing order and make BFS to fill level by level so i grantee smallest level to the greatest value ?

this is a simple greedy algorithm question.
just look for optimal binary search trees..
First sort all the numbers.
Consider each number is a tree node.
Take the two lowest numbers and make them as siblings. mark the parent with the sum of their values. and remove those from the set of numbers and put the new parent.
keep on doing this until only one node is left . which is the root of tree

why are we building BST when only binary tree is asked in question , sort the elements (nlogn) and then do a level order insertion from max to min will result in a minimum weight binary tree (not BST)