1130. Minimum Cost Tree From Leaf Values

Problem Description

The problem given asks us to construct binary trees based on certain conditions and calculate the sum of the values of each non-leaf node. The special conditions provided for the binary trees are:

• Each node in the tree either has no children (making it a leaf) or has exactly two children (non-leaf nodes).
• The sequence of values found at the leaf nodes must match the sequence given by array arr in an in-order traversal.
• For each non-leaf node, its value is determined as the product of the largest leaf value from its left subtree and the largest leaf value from its right subtree.

The goal is to find the binary tree which results in the smallest sum of the values of all the non-leaf nodes combined, and return this minimum possible sum. It's guaranteed that the result will fit within a 32-bit integer.

Intuition

The intuition behind the solution comes from the fact that constructing a tree with a lower sum of non-leaf nodes heavily depends on how we group the elements to form subtrees, and consequently, the products at non-leaf nodes. As such, we want to ensure that smaller numbers participate in more products while larger numbers should be used less often to keep the sum as small as possible.

A dynamic programming approach allows us to solve this efficiently. We can define a two-dimensional array f where f[i][j] represents the minimum sum of the values of non-leaf nodes for the subarray arr[i] to arr[j]. A companion array g stores the maximum leaf values we can have between indices i and j. This is done because we know that each non-leaf node's value equals the product of the largest leaf value in each of its left and right subtrees. So, g[i][j] helps us quickly determine those products as we build our solution.

By starting with subarrays of length 1 and extending to the full length of arr, we can systematically find the minimum sum for any given segment of arr. We do so by iterating through every possible division within a subarray, creating potential left and right subtrees, computing their respective non-leaf node value, and maintaining the minimum result for each segment.

The final answer will be the value of f[0][n - 1] which represents the minimum sum for the entire array arr converted into a binary tree following the described criteria.

Learn more about Stack, Greedy, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The implementation of the solution utilizes dynamic programming, which is a method to solve complex problems by breaking them down into simpler subproblems and solving each of these subproblems just once, storing their solutions – usually in an array.

Let’s dive into the step-by-step explanation of the code:

Step 1: Initialization

Two two-dimensional arrays, f and g, are initialized with dimensions n x n, where n is the length of the given array arr. Here, n represents the range of subarrays we will consider (from arr[i] to arr[j] inclusively):

• f[i][j] will store the minimum sum of the non-leaf nodes for the subarray arr[i] to arr[j].
• g[i][j] will store the maximum leaf value in the subarray arr[i] to arr[j].

1n = len(arr)
2f = [[0] * n for _ in range(n)]
3g = [[0] * n for _ in range(n)]

Step 2: Populate the g array

The g array is filled with the maximum leaf values. This step is crucial because it allows for quick access to the maximum leaf values later when calculating the non-leaf node values. To fill g, we iterate over all possible subarrays and populate g[i][j] with the maximum value between arr[j] and the current maximum g[i][j - 1]:

1for i in range(n - 1, -1, -1):
2    g[i][i] = arr[i]
3    for j in range(i + 1, n):
4        g[i][j] = max(g[i][j - 1], arr[j])

Step 3: Calculate the minimum sum of non-leaf nodes

The main logic for solving the problem resides here, where f[i][j] is computed for different subarrays. The idea is to iterate through all possible splits k of the subarray arr[i] to arr[j] into two parts, arr[i] to arr[k] and arr[k + 1] to arr[j]. For each split, we calculate:

• The sum of non-leaf nodes for both parts (f[i][k] and f[k + 1][j]), which have already been calculated thanks to the dynamic programming approach.
• The product of the maximum leaf values for the left and right subtrees (g[i][k] * g[k + 1][j]), which gives the value of the root for this particular binary tree formed by this split.

We keep track of the minimum sum obtained among all possible splits, and that becomes the value of f[i][j]:

1for i in range(n - 1, -1, -1):
2    for j in range(i + 1, n):
3        f[i][j] = min(
4            f[i][k] + f[k + 1][j] + g[i][k] * g[k + 1][j] for k in range(i, j)
5        )

Step 4: Return the result

Finally, f[0][n - 1] gives us the minimum sum for the entire array arr, and thus, is returned as the final result:

1return f[0][n - 1]

This implementation effectively breaks down the complex task of finding the optimal binary tree into manageable subproblems, whose results are stored and reused – demonstrating the efficacy of dynamic programming.

Example Walkthrough

Let's take a small example to illustrate how the solution approach works. Suppose we have the array arr given as [3, 11, 2, 5]. We want to construct a binary tree following the conditions mentioned and determine the minimum sum of non-leaf nodes' values.

Visualizing the Problem:

For arr = [3, 11, 2, 5], the in-order traversal of the leaf nodes in the binary tree must be [3, 11, 2, 5].

Step 1: Fill in g for maximum leaf values

We compute g[i][j] for all subarrays:

• For subarrays of length 1 (i.e., single elements), g[i][i] = arr[i].
• For longer subarrays, we would compute the maximum as follows:

1g[0][1] = max(arr[0], arr[1]) = max(3, 11) = 11
2g[1][2] = max(arr[1], arr[2]) = max(11, 2) = 11
3g[2][3] = max(arr[2], arr[3]) = max(2, 5) = 5

• And so on, for all subarray combinations.

Step 2: Populate g using dynamic programming

Here's the filled g matrix for our example array:

1g = [
2    [3, 11, 11, 11],
3    [0, 11, 11, 11],
4    [0,  0,  2,  5],
5    [0,  0,  0,  5]
6]

Step 3: Calculate f for minimum sums of non-leaf nodes

Now we need to compute f[i][j]. Being a dynamic programming solution, we start with the smallest subarrays and move to larger ones.

• For subarrays of length 1 (single elements), f[i][i] = 0, as single elements are leaf nodes and don't contribute to the sum of non-leaf nodes.
• Then we consider all subarrays of length 2 and above. For our example, let's compute f[0][2] which represents the subarray [3, 11, 2].

We would need to consider splitting this subarray into [3] and [11, 2] or [3, 11] and [2]. We'll compute the sum of non-leaf nodes for both scenarios:

For split [3] and [11, 2], the sum would be f[0][0] + f[1][2] + g[0][0] * g[1][2]. Here, f[0][0] and f[1][2] are 0 (since f is initialized with zeros and gets updated gradually), and g[0][0] * g[1][2] is 3 * 11.

For split [3, 11] and [2], the sum would be f[0][1] + f[2][2] + g[0][1] * g[2][2]. In this case f[0][1] and f[2][2] are again 0, and g[0][1] * g[2][2] is 11 * 2.

So, f[0][2] = min((0 + 0 + 3 * 11), (0 + 0 + 11 * 2)) = min(33, 22) = 22.

• We compute f[i][j] for all possible i and j in a similar fashion.

Step 4: Construct f matrix and determine the result

We proceed computing f values for increasingly larger subarrays of arr, keeping track of the minimum sum of non-leaf nodes using dynamic programming.

After filling out the f matrix, we'll get:

1f = [
2    [0, 33, 22, min_sum],
3    [0,  0, 22, min_sum],
4    [0,  0, 0, 10],
5    [0,  0, 0,  0]
6]

The min_sum in f[0][3] will be the final answer, which is computed by considering all the possibilities, as we just did for f[0][2].

By following these steps and populating f and g, we find that f[0][3] equals the minimum sum of the binary tree non-leaf nodes constructed from array arr, following the given conditions.

In this way, the dynamic programming solution helps us reduce the complexity of the problem by avoiding redundant calculations and focusing on subproblems, storing and reusing the solutions as the algorithm progresses.

Solution Implementation

Time and Space Complexity

The given code is a dynamic programming solution designed to minimize the sum of the products of non-leaf nodes' values in a binary tree built from an array, where each leaf is a value from the array. We'll analyze both time complexity and space complexity.

Time Complexity:

We have a nested loop where i goes from n-1 to 0 and for each i, j goes from i+1 to n, and within each pair of i and j, there is an inner loop where k goes from i to j-1. The time complexity can be evaluated as the sum of the series in the form of a cubic polynomial.

The number of times the innermost operation (the min calculation) is executed can be roughly approximated by the cubic sum Σ (i=1 to n) Σ (j=i+1 to n) Σ (k=i to j-1) 1, which simplifies to O(n^3) where n is the length of the array.

Thus, the time complexity of this solution is O(n^3).

Space Complexity:

The space complexity is determined by the two 2D arrays f and g which are each of size n*n, where n is the length of the input array arr. There are no other data structures that scale with the input size. Hence, the space complexity is O(n^2) due to these two 2D arrays.

Learn more about how to find time and space complexity quickly using problem constraints.