Minimum Cost Tree From Leaf Nodes

PROBLEM STATEMENT

Given an array/list ‘ARR' of size ‘N’, the task is to generate a Complete Binary Tree in such a way that the sum of the non-leaf nodes is minimum, whereas values of the leaf node correspond to the array elements in an In-order Traversal of the tree and value of each non-leaf node corresponds to the product of the largest leaf value in the left sub-tree and right sub-tree.

Example:

Let's say we have an 'ARR' = {1, 2, 3, 4}, so the possible complete 
binary trees will be:
   4                                                          12                      
  /  \                                                       /  \
 1   8                                                      6    4
     / \                                                   /  \
   2   12                                                  2   3   
        /  \                                              /  \
        3   4                                             1   2
  Sum of non-leaf nodes  = 24                    Sum of non-leaf nodes = 20
  So the required answer you have to return is 20.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of array elements.

The second line of every test case contains 'N' space-separated integers denoting the inorder traversal of leaf nodes of a complete binary tree.

Output format:

For each test case, return the minimum possible sum of non-leaf nodes of a binary tree.

Output for each test case is printed on a separate line.

Note:

1.You do not need to print anything, it has already been taken care of. Just return the minimum possible sum of all non-leaf nodes.

2. It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Constraints:

1 <= T <= 10
2 <= N <= 40
1 <= ARR[i] <= 15

Where ‘ARR[i]’ represents the array elements.

Time limit: 1 sec

Approach 1

Approach:

This is basically a recursive approach
Consider the array as an entire tree and each subarray[i ... j] represents subtree with leaves[i … j].
Now, for every start and end indexes, first put one element to the left and rest all in the right. Next, put 2 elements to left and rest all to the right and so on.
Here we will be using a pair that stores two values.
- The first one will be the max value of the leaf node in that subtree
- The second one will be the minimum value of the sum of non-leaf nodes from left to right subtrees.

Algorithm:

Create a function ‘treeSum’ which will return a pair of two integers. The function will contain three parameters starting index ‘STARTINDEX’, ending index ‘ENDINDEX’, and the array ‘ARR’.
Inside the ‘treeSum’ function:
- First, check whether it is a leaf node or not. For leaf node ('STARTINDEX' = ‘ENDINDEX’) and if so return pair of (Arr[i] , 0).
- Now create two variables ‘maxLeaf’ initialized to INT_MIN and ‘MINSUM’ initialized to INT_MAX.
- Now run a loop from ‘i’ = ‘STARTINDEX’ to ‘i' = ‘ENDINDEX’ and split the array at every ‘ith’ position and recursively call on the left subtree and right subtree.
  - ‘LEFT’ = treeSum('STARTINDEX', ‘i’ , ‘A') which will also be pair
  - ‘RIGHT’ = treeSum('i' + 1 , ‘ENDINDEX' , ‘A’) which will also be pair
  - ‘MAXLEAF’ = max('LEFT'.first , ‘RIGHT’.first)
  - ‘MINSUM’ = min('MINSUM' , ‘LEFT’.second + ‘RIGHT’.second +('LEFT'.first * ‘RIGHT’.first).
Finally return the answer as a pair of {'MAXLEAF', ‘MINSUM’}.second.

Try Problem

Approach 2

This is basically a recursive + memoization approach
Consider the array as an entire tree and each subarray[i ... j] represents subtree with leaves[i … j].
Now, for every start and end indexes, first put one element to the left and rest all in the right. Next, put 2 elements to left and rest all to the right and so on.
Here we will be using a pair that stores two values.
- The first one will be the max value of the leaf node in that subtree
- The second one will be the minimum value of the sum of non-leaf nodes from left to right subtrees.
Also while we will create a memo pad of pairs to store the answer whenever we return it from a recursive function call so that we do not calculate them again and again.

Algorithm:

Create a 2D array ‘MEMO’ which will store the pair of two integers. Initially, the whole array is initialized with a value of {INT_MIN, -1}.
Create a function ‘treeSum’ which will return pair of two integers. The function will contain three parameters starting index ‘STARTINDEX’, ending index ‘ENDINDEX’, and the array ‘ARR’.
Inside the ‘treeSum’ function:
- First, check whether it is a leaf node or not. For leaf node ('STARTINDEX' = ‘ENDINDEX’) and if so return pair of ('ARR'[i] , 0).
- Now before calculating the answer of the subproblem for the given ‘STARTINDEX’ and ‘ENDINDEX’ we will first check whether we have already a solution corresponding to the ('STARTINDEX', ‘ENDINDEX’). If we have the solution we would return the solution from here itself otherwise we would solve it.
- Now create two variables ‘MAXLEAF’ intialised to INT_MIN and ‘MINSUM’ intialised to INT_MAX.
- Now a run a loop from ‘i’ = ‘STARTINDEX’ to ‘i’ = ‘ENDINDEX’ and split the array at every ‘ith’ position and recursively call on the left subtree and right subtree.
  - ‘LEFT’ = treeSum('STARTINDEX', ‘i’ , ‘A’) which will also be pair
  - ‘RIGHT’ = treeSum('i' + 1 , ‘ENDINDEX’, ‘A’) which will also be pair
  - ‘MAXLEAF’ = max('LEFT'.first , ‘RIGHT’.first)
  - ‘MINSUM’ = min('MINSUM', ‘LEFT’.second + 'RIGHT'.second+('LEFT'.first * ‘RIGHT’.first).
Finally while returning the answer store them in the ‘MEMO’ array as a pair of {'MAXLEAF', ‘MINSUM’} for later use.

Try Problem

Approach 3

Approach:

This is basically an iterative dynamic programming approach
Consider the array as an entire tree and each subarray[i ... j] represents subtree with leaves[i … j].
Now, for every start and end index, first put one element to the left and rest all on the right. Next, put 2 elements to left and rest all to the right, and so on.
Here we will be using a pair that stores two values.
- The first one will be the max value of the leaf node in that subtree
- The second one will be the minimum value of the sum of non-leaf nodes from left to right subtrees.
Let ‘DP’[i][j] will be our dynamic programming matrix to store the pair.
The relation that we will be using is:
- ‘DP’[left][right] is the sum(minimum) of all non-leaf nodes from left to right
- ‘DP’[left][right] = Dp[left][K] + Dp[k+][right] + (value of the node that splits the subtree 'left to right' into subtrees 'left to K' and 'K + 1 to right' = min(max(left,'K') * max('K'+1,right))
- ‘DP’[left][k] will compute the sum of non-leaf nodes of the subarray with leaves from [left, 'K']. Similarly is for ‘DP’[right, ‘K’].
‘DP’[i][j].first = max of the subarray
‘DP’[i][j].second = minimum sum of all the non-leaf nodes from left to right.

Algorithm:

Firstly, create a 2D array of pairs to all initialized to zero.
Then we have to fill the base cases first that is when ‘i’ == ‘j’ and the length of each subarray('L') are equal to 1.
- Run a for loop from ‘i’ = 0 to ‘i’ = ‘’N' - 1 and do ‘DP’[i][i].first = ‘ARR’[i]
- For the subarray j = i+1 to j = n-1 do Dp[i][j].first = max(Dp[i][j-1].first , Arr[j])
Now for each length of the subarray starting from ‘L’ = 2 to ‘L’ = ‘N’ we will perform the following steps:
- Now for each ‘L’ we run a another for loop from ‘i’ = 0 to ‘i’ = ‘N’ -'L' + 1.Inside this loop:
  - We calculate the ending index of the subarray ‘j’ which is equal to ‘i’ + ‘L’ - 1.
  - Now for the subarray from ‘K’ = ‘i’ to ‘K’ = ‘j’ - 1 we will find the minimum sum and store it in ‘DP’[i][j].
  - ‘DP’[i][j].second = min('DP'[i][j].second, ‘DP’[i][k].second + 'DP'[k+1][j].second + ‘DP’[i][k].first * ‘DP’[k+1][j].first).
Finally, return the answer which is equal to ‘DP’[0]['N' - 1].second.

Try Problem

Approach 4

The steps are as follows:

Since the sum of non-leaf nodes should be minimized, therefore we require that the sum of the products be minimized, and the smallest nodes at both ends of the nodes are selected to be merged into a subtree, and the value is constructed as the product of the two. So we will be using a monotonically decreasing stack for this.
This is basically a greedy approach.
Each time two adjacent elements will form a subtree and a smaller element will be removed leaving only the larger elements.
So in order to remove ‘ARR’[i], it will require a cost of ‘ARR’[i] * min('LEFT', ‘RIGHT’) where ‘LEFT’ is the largest element on the left subtree and ‘RIGHT’ is the largest element on the right subtree of node ‘ARR’[i].
For example, 2 in [6,2,4] is the local minimum element because it is smaller than the elements on the left and right sides. We multiply the local minimum element with the smaller element on both sides and add it to the answer and erase the local minimum element at the same time.

Algorithm:

First, create a stack ‘ST’ to store the array elements. Initially push ‘INT_MAX’ into the stack ‘ST’ in order to avoid any boundary-value situation.
Also, create an ‘ANS’ variable to store the result.
Now start traversing on the array ‘ARR’.
- If the current element is less than the top of the stack then directly push that element into the stack ‘ST’.
- Otherwise, the current top of the stack is the local minimum element.
- Store the top of the stack in a ‘TEMP’ variable. Pop that element from stack ‘ST’.
- Then add to the ‘ANS’ ('TEMP' * min(Top of the Stack, ‘ARR’[i]))
- Repeat the above two operations until the top of the stack ‘ST’ element is less than equal to the ‘ARR'[i]
After processing the whole array, if there are more than two elements in the stack, we will first store the top of the stack in another ‘TEMP’ variable and then pop the top of the stack. And then add to the ‘ANS’ ('TEMP' * Top of the stack).
Finally, return the ‘ANS’ as the answer.

EXAMPLE:

{6,2,4,8} ‘ANS' = 0

{6,4,8} ‘ANS’ = 8 (2*min(6 , 4))

{6,8} ‘ANS’ = 8 + 24(4*min(6 , 8))

{8} ‘ANS’ = 8 + 24 + 48(6*8)

Try Problem