Minimum Cost Tree From Leaf Nodes

Hard
0/120
Average time to solve is 20m
profile
Contributed by
11 upvotes
Asked in companies
MicrosoftGoldman Sachs

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
1 2 3 4
3
6 2 4
Sample Output 1:
20
32
Explanation for Sample Output 1:
In test case 1, It is already explained above in the example.

In test case 2, There are two possible trees. The first has a non-leaf node sum of 36, and the second has a non-leaf node sum of 32. So the required answer is 32

       24                24
      /  \              /  \
     12   4             6    8
     /\                     / \
   6    2                  2   4
Sample Input 2:
2
3
5 2 3
4
5 3 2 1
Sample Output 2:
 21
 23
Hint

Try to solve the problem by breaking it into subproblems(recursive approach)

Approaches (4)
Recursion

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.
Time Complexity

 O(2^N),  Where ‘N’ is the number of leaf nodes. 

 

Since we are using a recursive function to find the minimum sum where we are comparing each subarray maximum value and from it calculating the minimum sum. So the overall time complexity will be O(2^N). 

Space Complexity

O(N), Where ‘N’ is the number of leaf nodes.

 

Since we are using a recursive function and in the worst case, there can be O(N) states in the call stack, the overall space complexity will be O(N). 

Code Solution
(100% EXP penalty)
Minimum Cost Tree From Leaf Nodes
Full screen
Console