Skip to main content

1130. Minimum Cost Tree From Leaf Values

medium

Given the leaves of a strict binary tree in order, build the tree so the sum of (max-left * max-right) over internal nodes is minimum. Classic interval DP — also a famous monotonic-stack optimization problem.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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; 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.

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 2^31).

Examples

Example 1

Input
arr = [6,2,4]
Output
32

Explanation: 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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Interval DP. dp[i][j] = minimum sum of non-leaf values for the subtree spanning arr[i..j].

Hint 2

Precompute maxRange[i][j] = max(arr[i..j]) — needed for the internal-node value at every split.

Hint 3

Recurrence: dp[i][j] = min over split k in [i, j) of dp[i][k] + dp[k+1][j] + maxRange[i][k] * maxRange[k+1][j].

Hint 4

Greedy alternative with a monotonic stack pops every local-minimum leaf and multiplies it by the smaller of its two larger neighbors — O(n).

Solution approach

Reveal approach

Interval DP. dp[i][j] is the minimum non-leaf sum for the subtree whose leaves are arr[i..j] in order. Precompute maxRange[i][j] for O(1) max-of-interval queries. Fill in increasing interval length. For each (i, j), try every split point k in [i, j); the cost is dp[i][k] + dp[k+1][j] + maxRange[i][k] * maxRange[k+1][j]. Take the min. Base case: dp[i][i] = 0 (a single leaf has no non-leaf nodes). Return dp[0][n-1]. Time O(n^3). Greedy alternative: a monotonic stack approach achieves O(n) by repeatedly removing the smallest local element and pairing it with the smaller of its two larger neighbors.

Complexity

Time
O(n^3)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • interval-dp
  • monotonic-stack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Minimum Cost Tree From Leaf Values and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →