Minimum Cost Tree From Leaf Values

medium monotonic stack greedy array

Problem

Given an array arr of positive integers, build a binary tree whose leaves are the array values in order (left to right). Each internal node's value is the product of the largest leaf in its left subtree and the largest leaf in its right subtree. Return the smallest possible sum of all internal node values.

Key idea: each value will eventually be "merged away" by pairing it with a neighbour; the merge cost is removed × larger-neighbour. To minimise total cost, greedily remove the smallest leaf first, pairing it with the smaller of its two neighbours. A monotonic (decreasing) stack does this in one pass.

Inputarr = [6, 2, 4]

Output32

Remove 2 (smallest), pairing with min(6, 4) = 4 → cost 2×4 = 8. Now [6, 4]: remove 4, pair with 6 → cost 4×6 = 24. Total 8 + 24 = 32.

arr (comma-separated)

def mctFromLeafValues(arr):
    total = 0
    stack = [float('inf')]
    for x in arr:
        while stack[-1] <= x:
            mid = stack.pop()
            total += mid * min(stack[-1], x)
        stack.append(x)
    while len(stack) > 2:
        total += stack.pop() * stack[-1]
    return total

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

class Solution {
    public int mctFromLeafValues(int[] arr) {
        int total = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(Integer.MAX_VALUE);
        for (int x : arr) {
            while (stack.peek() <= x) {
                int mid = stack.pop();
                total += mid * Math.min(stack.peek(), x);
            }
            stack.push(x);
        }
        while (stack.size() > 2) {
            total += stack.pop() * stack.peek();
        }
        return total;
    }
}

int mctFromLeafValues(vector<int>& arr) {
    int total = 0;
    vector<int> stack = { INT_MAX };
    for (int x : arr) {
        while (stack.back() <= x) {
            int mid = stack.back(); stack.pop_back();
            total += mid * min(stack.back(), x);
        }
        stack.push_back(x);
    }
    while ((int)stack.size() > 2) {
        int mid = stack.back(); stack.pop_back();
        total += mid * stack.back();
    }
    return total;
}

Explanation

Every leaf eventually gets "merged" with a neighbor, and that merge costs removed_value × larger_neighbor. To keep the total small, we want to remove small leaves early and pair each with its smaller neighbor, so the big values get reused as few times as possible. A monotonic decreasing stack turns this greedy idea into one clean pass.

We seed the stack with a sentinel inf so it never empties. For each value x, while the stack top is <= x, that top is a local minimum trapped between two larger numbers — we pop it as mid and add mid * min(stack_top, x) to the total, pairing it with the smaller of its two neighbors.

After popping, we push x. This keeps the stack decreasing. At the very end, whatever is left is already in decreasing order, so we merge them from top down, each costing top * next.

Example: arr = [6, 2, 4]. When 4 arrives, 2 is on top and 2 <= 4, so we pop 2 and add 2 * min(6, 4) = 8. The leftover stack [inf, 6, 4] then merges 4 * 6 = 24. Total is 8 + 24 = 32.

Removing each small value next to its smaller neighbor is exactly what minimizes how often large leaf values get multiplied, which is why the greedy stack gives the optimal sum.

Time: O(n) Space: O(n)