Minimum Cost Tree From Leaf Values

Problem

Given a positive integer array arr representing the in-order traversal of leaves of a binary tree, consider every binary tree where each internal node's value equals the product of the largest leaf in its left subtree and the largest leaf in its right subtree. Return the minimum possible sum of all internal-node values.

Intuition

Two lines of attack. Start with interval DP and let a structural observation drag you to something much faster.

Interval DP (O(n³)). dp[l][r] = the minimum total internal-node cost for the subtree whose leaves are arr[l..=r]. For a single leaf the cost is 0; otherwise split somewhere:

dp[l][r] = min_{k in [l, r)} dp[l][k] + dp[k+1][r] + max(arr[l..=k]) * max(arr[k+1..=r])

Precompute max_range[l][r] and you get O(n²) states × O(n) split choices = O(n³). Works for the LC input size (n ≤ 40), but doesn't scale.

Monotonic stack (O(n)). Here's the structural observation: every internal node's value contains the larger of two adjacent leaves, each multiplied by some neighbor. Think about it greedily — the optimal tree should pair each small leaf with its smaller adjacent greater, so the expensive big leaves are each used only once.

Concretely, scan arr left-to-right, keeping a monotonically decreasing stack. For each new value x:

• While the stack top is ≤ x, pop it. At that moment the popped leaf's "pairing" becomes min(left_neighbor_on_stack_or_infinity, x). Add popped * min(...) to the answer.
• Push x.

At end, pop the remaining stack multiplying adjacent pairs. Each leaf contributes exactly once, paired with its smaller adjacent greater — exactly the same quantity the interval DP computes, but in a single pass.

If you're thinking "this looks like #739 Daily Temperatures" — yes, it's the same monotonic-stack template. When you find a greater element to the right, you've identified the "next smaller greater" for everything it pops off.

Approach

impl Solution {
    pub fn mct_from_leaf_values(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut max_range = vec![vec![0i32; n]; n];
        for l in 0..n {
            max_range[l][l] = arr[l];
            for r in (l + 1)..n {
                max_range[l][r] = max_range[l][r - 1].max(arr[r]);
            }
        }
        let mut dp = vec![vec![0i32; n]; n];
        for len in 2..=n {
            for l in 0..=(n - len) {
                let r = l + len - 1;
                let mut best = i32::MAX;
                for k in l..r {
                    let cost = dp[l][k] + dp[k + 1][r] + max_range[l][k] * max_range[k + 1][r];
                    if cost < best {
                        best= cost;
                    }
                }
                dp[l][r]= best;
            }
        }
        dp[0][n - 1]
    }
}

function mctFromLeafValues(arr: number[]): number {
  const n = arr.length;
  const maxRange: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let l = 0; l < n; l++) {
    maxRange[l][l] = arr[l];
    for (let r = l + 1; r < n; r++) {
      maxRange[l][r] = Math.max(maxRange[l][r - 1], arr[r]);
    }
  }
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let len = 2; len <= n; len++) {
    for (let l = 0; l + len - 1 < n; l++) {
      const r = l + len - 1;
      let best = Infinity;
      for (let k = l; k < r; k++) {
        const cost = dp[l][k] + dp[k + 1][r] + maxRange[l][k] * maxRange[k + 1][r];
        if (cost < best) best = cost;
      }
      dp[l][r] = best;
    }
  }
  return dp[0][n - 1];
}

impl Solution {
    pub fn mct_from_leaf_values(arr: Vec<i32>) -> i32 {
        let mut stack: Vec<i32> = vec![i32::MAX];
        let mut total: i32 = 0;
        for x in arr {
            while *stack.last().unwrap() <= x {
                let popped= stack.pop().unwrap();
                let left= *stack.last().unwrap();
                total = popped * left.min(x);
            }
            stack.push(x);
        }
        // Drain the rest: each leaf pairs with its left neighbor.
        while stack.len() > 2 {
            let popped = stack.pop().unwrap();
            let left = *stack.last().unwrap();
            total += popped * left;
        }
        total
    }
}

function mctFromLeafValues(arr: number[]): number {
  const stack: number[] = [Infinity];
  let total = 0;
  for (const x of arr) {
    while (stack[stack.length - 1] <= x) {
      const popped = stack.pop() as number;
      const left = stack[stack.length - 1];
      total += popped * Math.min(left, x);
    }
    stack.push(x);
  }
  while (stack.length > 2) {
    const popped = stack.pop() as number;
    const left = stack[stack.length - 1];
    total += popped * left;
  }
  return total;
}

Trace

Monotonic stack on arr = [6, 2, 4]:

Return 32. ✓

Edge cases

• Length 1 — return 0. One leaf has no internal nodes. The main loop doesn't execute; the drain loop can't pop past the sentinel.
• Length 2 — return arr[0] * arr[1]. One internal node.
• Strictly increasing input — the stack keeps growing; the drain loop pairs them down right-to-left. Each leaf multiplies with its right neighbor.
• Strictly decreasing input — every x triggers a pop. Each leaf multiplies with the smaller of (its immediate successor, its immediate predecessor on the stack).

Takeaway

When an O(n³) interval DP hides a local greedy structure, a monotonic stack can collapse it to O(n). The trick is spotting the invariant: here, every value gets paired with a single specific neighbor in the optimal tree. Not every interval DP has that property — if the optimal split depends on non-local information (as in #312 Burst Balloons, where the last-to-burst decision involves the whole interval), the stack approach fails and you're back to O(n³) DP.

But when the greedy structure is there, the improvement is dramatic. Watch for problems of the form "minimize a sum of pairwise products" where each leaf has a natural neighbor relation — that's the fingerprint.