Min Cost Tree From Leaf Values LeetCode 1130

LeetCode 1130 — Minimum Cost Tree From Leaf Values — gives you an array arr of positive integers. You must build a binary tree where the leaves correspond to arr in left-to-right order. Each non-leaf node's value equals the product of the maximum leaf value in its left subtree and the maximum leaf value in its right subtree. Minimize the sum of all non-leaf node values.

The tree structure is flexible — you choose where to split the array at each level. Splitting arr[0..k] as the left subtree and arr[k+1..n-1] as the right subtree defines one possible tree. Different split points yield different non-leaf sums.

While this looks like an interval DP problem (and it can be solved that way in O(n^3)), the greedy insight reduces it to O(n): always pair the smallest remaining leaf with its smaller neighbor first, because small leaves contribute less to the total cost when eliminated early.

Think of building the tree bottom-up. Each time two adjacent leaves merge into a non-leaf node, the cost is their product (specifically max_left * max_right, but for two leaves that is just their product). The smaller leaf is then "consumed" — it no longer participates in future products.

To minimize total cost, we want small values to participate in as few products as possible. The smallest leaf should be consumed first, paired with its smaller neighbor. This way, the small value appears in exactly one product, and that product is as small as possible.

After consuming the smallest leaf, the remaining leaves form a smaller array. Repeat: find the new smallest, pair it with its smaller neighbor, add the cost. Continue until one leaf remains. The sum of all costs is the minimum non-leaf sum.

The greedy removal can be implemented efficiently with a monotonic decreasing stack. Push elements onto the stack. When the current element is larger than the stack top, the top is a local minimum — it should be consumed. Pop it and pair it with the smaller of its two neighbors: the new stack top and the current element.

The cost of consuming the popped element mid is mid * min(stack.peek(), current). Add this cost to the running total. Continue popping while the stack top is less than or equal to the current element. Then push the current element.

After processing all elements, the stack is monotonically decreasing. Pop remaining elements one by one, each paired with the new top (its only remaining neighbor). This handles the final merge sequence.

Consider arr = [6, 2, 4]. Stack starts with sentinel [Infinity]. Push 6: stack = [Inf, 6]. Push 2: 2 < 6, push. Stack = [Inf, 6, 2]. Current = 4: 4 > 2, pop 2. Cost += 2 * min(6, 4) = 2*4 = 8. Stack top is 6, 4 < 6, push 4. Stack = [Inf, 6, 4].

No more elements. Clean up stack: pop 4, pair with 6. Cost += 4*6 = 24. Stack = [Inf, 6]. Pop 6, pair with Inf — skip (sentinel). Total cost: 8 + 24 = 32.

Verify with interval DP: split at k=0: left=[6], right=[2,4]. Right subtree cost = 2*4=8, root = 6*4=24. Total = 8+24 = 32. Split at k=1: left=[6,2], right=[4]. Left cost = 6*2=12, root = 6*4=24. Total = 12+24 = 36. Minimum is 32, matching the greedy result.

In Python, initialize stack = [float('inf')] and result = 0. For each val in arr: while stack[-1] <= val, pop mid and add mid * min(stack[-1], val). Push val. After the loop, while len(stack) > 2, pop and add popped * stack[-1]. Return result.

In Java, use an ArrayDeque<Integer> with Integer.MAX_VALUE as sentinel. The while loop and cleanup logic are identical. Use Math.min for neighbor comparison. Accumulate the result in a long to avoid overflow concerns.

The interval DP alternative uses dp[i][j] = min cost for subarray arr[i..j]. For each split point k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + max(arr[i..k]) * max(arr[k+1..j])). This runs in O(n^3) time and O(n^2) space — correct but much slower than the stack approach.

The monotonic stack solution runs in O(n) time. Each element is pushed once and popped once. The cleanup phase also pops at most n elements. Total operations are bounded by 2n.

Space complexity is O(n) for the stack in the worst case (strictly decreasing input). On average, the stack size is much smaller because elements get consumed by larger values arriving later.

The greedy simulation (finding and removing the minimum each time) runs in O(n^2) without a stack. The stack optimizes this by processing removals in order of natural stack eviction rather than searching for the minimum.

Sum of Subarray Minimums (LeetCode 907) uses the same monotonic stack technique to process local minima. Both problems pop elements when they are "dominated" by their neighbors and compute a cost at pop time. The structural similarity is striking.

Burst Balloons (LeetCode 312) is the classic interval DP problem with a similar flavor: choose an order to process elements that minimizes (or maximizes) total cost. The DP approach for Minimum Cost Tree follows the same interval DP template.

Maximum Binary Tree (LeetCode 654) builds a tree from an array using max values as roots. While the construction rule differs, both problems connect array operations to tree structures — a theme worth practicing across multiple problems.