Minimum Cost Tree From Leaf Values Medium 0 attempts
LeetCode ↗

Minimum Cost Tree From Leaf Values

Medium Stack&Queue LeetCode

You're given an array arr, and each of its values becomes a leaf of a binary tree, placed left to right so that reading the leaves in order reproduces arr. Every internal node's value equals the product of the largest leaf in its left subtree and the largest leaf in its right subtree. Build the tree so that the total value stored across the internal (non-leaf) nodes is as small as possible, and return that minimum sum.

Every internal node has exactly two children.

Input Format
Implement mctFromLeafValues(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
arr = [6,2,4]
Output
32

Example 2

Input
arr = [4,11]
Output
44
Constraints
  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
Test Cases (2)
Case 1
Args: [[6,2,4]] Expected: 32
Case 2
Args: [[4,11]] Expected: 44
Topics
Stack&Queue

Monotonic Stack (Greedy)

javascript
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