Minimum Cost Tree From Leaf Values Medium 0 attempts
LeetCode ↗

Minimum Cost Tree From Leaf Values

Medium Stack&Queue LeetCode

Given an array where each leaf of the tree holds one value, build a binary tree such that each non-leaf node's value is the product of the largest leaf values of its left and right subtrees. Minimize the sum of non-leaf nodes.

Example: arr = [6,2,4] → Output: 32

Sample Input
—
Sample Output
—
Constraints
  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
Topics
Stack&Queue

Monotonic Stack (Greedy)

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

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

Saved in this browser only. Private to you.

JavaScript