Minimum Cost Tree From Leaf Values — Medium Problem & Solution

Build a binary tree where every node has either 0 or 2 children and the leaves, read left to right, spell out arr.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Greedy, Stack, Monotonic Stack
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Build a binary tree where every node has either 0 or 2 children and the leaves, read left to right, spell out arr. Each non-leaf 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 the non-leaf node values.

Example 1

Input: arr = [6,2,4]
Output: 32
Explanation: Pair 2 with 4 first (cost 8), then 6 with 4 (cost 24).

Example 2

Input: arr = [4,11]
Output: 44
Explanation: Only one tree exists.

Example 3

Input: arr = [1,2,3,4]
Output: 20

Constraints

2 <= arr.length <= 40
1 <= arr[i] <= 15
The answer fits in a signed 32-bit integer.

How to solve Minimum Cost Tree From Leaf Values

Think of it as repeatedly merging adjacent leaves: merging costs the product and replaces the pair with the larger value. Every element must eventually be merged away except the overall maximum, and the cheapest moment to remove a value is against the smaller of its two neighbours.

Approach

Keep a stack that is decreasing from bottom to top.
For each new value, pop while the top is at most the new value: that popped element is a local minimum, so pay popped × min(newTop, incoming).
Push the new value; at the end, drain the stack paying popped × nextBelow.

Why it works

Removing value v costs v × (one of its neighbours), and the cheaper neighbour is always the better choice — the larger neighbour survives to be paired later anyway. The monotonic stack pops exactly when both neighbours of an element are known, so each element is charged once, against the smaller of the two. That greedy is optimal, and matches the O(n³) interval DP that the problem's tree framing suggests.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

Paying against the larger neighbour instead of the smaller over-counts.
The final drain must not be forgotten — the remaining stack is still decreasing.
The O(n³) interval DP is also correct but much slower.

Reference solution

Python

from typing import List

def mctFromLeafValues(arr: List[int]) -> int:
    st = []
    res = 0
    for x in arr:
        while st and st[-1] <= x:
            mid = st.pop()
            res += mid * (min(st[-1], x) if st else x)
        st.append(x)
    while len(st) > 1:
        res += st.pop() * st[-1]
    return res

JavaScript

var mctFromLeafValues = function(arr) {
    var st = [];
    var res = 0;
    for (var i = 0; i < arr.length; i++) {
        var x = arr[i];
        while (st.length > 0 && st[st.length - 1] <= x) {
            var mid = st.pop();
            if (st.length > 0) res += mid * Math.min(st[st.length - 1], x);
            else res += mid * x;
        }
        st.push(x);
    }
    while (st.length > 1) {
        var a = st.pop();
        res += a * st[st.length - 1];
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue