Interview AiBox logo
Interview AiBox
#1130
Medium
auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Cost Tree From Leaf Values

Compute the minimum sum of non-leaf nodes in a binary tree formed from array leaves using dynamic programming efficiently.

arraydynamic programmingstackgreedymonotonic stack
category

5

Topics

code_blocks

5

Code langs

hub

3

Related

play_arrowStart Solutionarrow_forward
speedComplexityopen_in_newLeetCode

Practice Focus

Medium · State transition dynamic programming

bolt

Answer-first summary

Compute the minimum sum of non-leaf nodes in a binary tree formed from array leaves using dynamic programming efficiently.

Interview AiBox logo

Ace coding interviews with Interview AiBox guidance for State transition dynamic programming

Try AiBox Copilotarrow_forward

This problem asks for constructing a binary tree from an array of positive integers while minimizing the sum of all non-leaf nodes. Using a state transition dynamic programming approach, you can systematically compute subarray solutions and combine them to get the global minimum. Careful handling of subarray maxima and memoization ensures correct results within feasible time limits.

Problem Statement

Given an array of positive integers representing leaf node values, construct all possible binary trees where each leaf corresponds to an element in the array. Every non-leaf node's value is the product of the largest leaf values in its left and right subtrees. Compute the minimum possible sum of all non-leaf node values across all valid trees.

Return the smallest sum of non-leaf node values for any binary tree built from the array. Each node is a leaf if and only if it has no children, and the array length is guaranteed to be between 2 and 40, with each element between 1 and 15.

Examples

Example 1

Input: arr = [6,2,4]

Output: 32

There are two possible trees shown. The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.

Example 2

Input: arr = [4,11]

Output: 44

Example details omitted.

Constraints

  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
  • It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 231).

Solution Approach

Dynamic Programming on Subarrays

Define dp(i, j) as the minimum sum of non-leaf nodes for subarray arr[i..j]. For each subarray, try all possible partitions k where i <= k < j, and recursively compute dp(i, k) + dp(k+1, j) + max(arr[i..k]) * max(arr[k+1..j]). Store results in a memo table to avoid recomputation.

Monotonic Stack Optimization

Instead of full DP, use a monotonic decreasing stack to greedily combine smaller leaves first. Push each leaf onto the stack, and whenever the current leaf is greater than the stack top, pop and accumulate the product with the smaller neighbor. This produces the minimum non-leaf sum efficiently in O(n) time.

Handling Edge Cases and Small Arrays

For arrays of length two, the solution is simply arr[0] * arr[1]. Ensure that when computing subarray maxima or combining stack elements, indices are correctly managed to prevent overcounting. These details prevent subtle DP failures and stack miscalculations.

Complexity Analysis

Metric Value
Time Depends on the final approach
Space Depends on the final approach

The DP approach has O(n^3) time due to considering all subarrays and all partitions, and O(n^2) space for memoization. The monotonic stack approach reduces time to O(n) with O(n) space. Both respect the problem's constraint that n <= 40.

What Interviewers Usually Probe

  • Do you consider overlapping subproblems for the subarray DP?
  • Can you reduce the O(n^3) DP with a greedy or stack-based method?
  • How do you maintain maximum leaf values efficiently during subarray merges?

Common Pitfalls or Variants

Common pitfalls

  • Forgetting to correctly compute max(arr[i..k]) and max(arr[k+1..j]) in DP can inflate the sum.
  • Incorrect stack handling can merge the wrong neighbors, giving a larger non-leaf sum.
  • Not memoizing subarray results leads to TLE on larger arrays up to 40 elements.

Follow-up variants

  • Minimizing non-leaf sum when node value is the sum of maximum leaves instead of product.
  • Finding maximum non-leaf sum instead of minimum for the same leaf array.
  • Allowing leaves to appear multiple times, requiring adjusted DP state.

FAQ

What pattern is used to solve Minimum Cost Tree From Leaf Values?

The problem uses state transition dynamic programming on subarrays and can be optimized with a monotonic stack for greedy merging.

Can this problem be solved faster than standard DP?

Yes, using a monotonic stack reduces time complexity from O(n^3) to O(n) while preserving the minimum sum computation.

How do you handle arrays with only two elements?

Simply compute the product of the two elements as the single non-leaf node value.

Why is memoization important in DP approach?

Memoization prevents recalculating subarray results, avoiding exponential recomputation and ensuring feasibility for n up to 40.

What common mistake leads to incorrect minimum sum?

Miscalculating subarray maximums or incorrectly merging stack elements often produces a sum larger than the true minimum.

terminal

Solution

Solution 1: Memoization Search

According to the problem description, the values in the array $arr$ correspond one-to-one with the values in the inorder traversal of each leaf node of the tree. We can divide the array into two non-empty sub-arrays, corresponding to the left and right subtrees of the tree, and recursively solve for the minimum possible sum of all non-leaf node values in each subtree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> Tuple:
            if i == j:
                return 0, arr[i]
            s, mx = inf, -1
            for k in range(i, j):
                s1, mx1 = dfs(i, k)
                s2, mx2 = dfs(k + 1, j)
                t = s1 + s2 + mx1 * mx2
                if s > t:
                    s = t
                    mx = max(mx1, mx2)
            return s, mx

        return dfs(0, len(arr) - 1)[0]

Solution 2: Dynamic Programming

We can change the memoization search in Solution 1 to dynamic programming.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> Tuple:
            if i == j:
                return 0, arr[i]
            s, mx = inf, -1
            for k in range(i, j):
                s1, mx1 = dfs(i, k)
                s2, mx2 = dfs(k + 1, j)
                t = s1 + s2 + mx1 * mx2
                if s > t:
                    s = t
                    mx = max(mx1, mx2)
            return s, mx

        return dfs(0, len(arr) - 1)[0]

Solution 3

#### Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> Tuple:
            if i == j:
                return 0, arr[i]
            s, mx = inf, -1
            for k in range(i, j):
                s1, mx1 = dfs(i, k)
                s2, mx2 = dfs(k + 1, j)
                t = s1 + s2 + mx1 * mx2
                if s > t:
                    s = t
                    mx = max(mx1, mx2)
            return s, mx

        return dfs(0, len(arr) - 1)[0]

Continue Practicing

#1526 minimum number of increments on subarrays to form a target array#975 odd even jump#907 sum of subarray minimums
category

Continue Topic

array

Practice more edge cases under the same topic.

arrow_forwardauto_awesome

Continue Pattern

State transition dynamic programming

Expand the same solving frame across more problems.

arrow_forwardsignal_cellular_alt

Same Difficulty Track

Medium

Stay on this level to stabilize interview delivery.

arrow_forward
Minimum Cost Tree From Leaf Values Solution: State transition dynamic programming | LeetCode #1130 Medium