Minimum Cost Tree From Leaf Values

Medium
880.

Minimum Cost Tree From Leaf Values

Minimum Cost Tree From Leaf Values is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google, Uber and MathWorks interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var mctFromLeafValues = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost Tree From Leaf Values — Problem & Solution

Minimum Cost Tree From Leaf Values solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Cost Tree From Leaf Values is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google, Uber and MathWorks interviews.

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.

Hints for Minimum Cost Tree From Leaf Values

  1. Hint 1

    Merging two adjacent leaves costs the product of their values and leaves the larger one behind.

  2. Hint 2

    So the smallest value should be merged away first, against its smaller neighbour.

  3. Hint 3

    A decreasing monotonic stack does exactly that in one pass.

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

  1. Keep a stack that is decreasing from bottom to top.
  2. 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).
  3. 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

Java

public static int mctFromLeafValues(int[] arr) {
    Deque<Integer> st = new ArrayDeque<>();
    int res = 0;
    for (int x : arr) {
        while (!st.isEmpty() && st.peek() <= x) {
            int mid = st.pop();
            res += mid * (st.isEmpty() ? x : Math.min(st.peek(), x));
        }
        st.push(x);
    }
    while (st.size() > 1) {
        int a = st.pop();
        res += a * st.peek();
    }
    return res;
}

C++

int mctFromLeafValues(vector<int>& arr) {
    vector<int> st;
    int res = 0;
    for (int x : arr) {
        while (!st.empty() && st.back() <= x) {
            int mid = st.back();
            st.pop_back();
            res += mid * (st.empty() ? x : min(st.back(), x));
        }
        st.push_back(x);
    }
    while (st.size() > 1) {
        int a = st.back();
        st.pop_back();
        res += a * st.back();
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming