Minimum Cost Tree From Leaf Values - Leetcode Solution

Problem Statement:

Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children; The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.) The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively. Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

Example:

Input: arr = [6,2,4] Output: 32 Explanation: There are two possible trees. The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

Solution:

The problem can be solved using dynamic programming. We can define a dp array where dp[i][j] represents the minimum sum of non-leaf nodes that can be obtained between the i-th and j-th leaf nodes.

For each subarray of size 1, the value of dp[i][i] will be 0 because there are no non-leaf nodes in a single node tree.

For each subarray of size 2, the value of dp[i][i+1] will be the product of the two leaf values because there is only one non-leaf node in a two-node tree.

For subarrays of size greater than 2, we can break the array into two subarrays and find the minimum sum of non-leaf nodes for both subarrays. We can then combine these two results to form the final result.

Let's define a variable called max_value that represents the maximum leaf value between the i-th and j-th leaf nodes. We can find this value by iterating through the subarray and finding the maximum value.

For each k between i and j-1, we can compute the minimum sum of non-leaf nodes for the subarray i to k and the subarray k+1 to j. The sum will be dp[i][k] + dp[k+1][j] + max_value * max_value.

We can try every value of k and take the minimum of all these results to get the final result for dp[i][j].

The final answer will be in dp[0][n-1] where n is the length of the array.

Here is the code implementation for the same:

int mctFromLeafValues(vector<int>& arr) { int n = arr.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for(int len=2; len<=n; len++){ for(int i=0; i<=n-len; i++){ int j=i+len-1; dp[i][j] = INT_MAX; int max_value = 0; for(int k=i; k<j; k++){ max_value = max(max_value, arr[k]); dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + max_value * max_value); } } } return dp[0][n-1]; }

Time Complexity: O(n^3)

1