Minimum Cost Tree From Leaf Values: Monotonic Stack Pattern

LeetCode's Minimum Cost Tree From Leaf Values (problem 1130) looks like a tree problem, but the real trick is recognizing that you never need to build a tree at all. It is rated medium, and the optimal solution uses a monotonic stack to greedily pair adjacent leaf values, turning a seemingly complex tree-construction problem into a clean single-pass algorithm.

The problem

You are given an array arr of positive integers. You need to build a binary tree such that:

1. Each leaf node has a value from arr, and the leaves read left to right match arr exactly (the in-order traversal of leaves equals arr).
2. Each non-leaf (internal) node has a value equal to the product of the maximum leaf value in its left subtree and the maximum leaf value in its right subtree.

Return the minimum possible sum of all non-leaf node values.

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

The optimal tree pairs leaves [2, 4] together first (internal node = 2 * 4 = 8), then pairs that subtree with leaf 6 (internal node = 6 * 4 = 24). Total cost = 8 + 24 = 32.

Why this is really a pairing problem

Here is the key insight. Every time you create an internal node, you are "consuming" a leaf by pairing it with an adjacent leaf (or subtree). The cost of that consumption is the leaf's value multiplied by the maximum of its neighbor. Once consumed, the leaf disappears from the array, and the neighbor's maximum carries forward.

Think of it this way: the smallest leaf in the array contributes the least to the total cost. You want to "remove" it as early as possible by pairing it with its smaller neighbor. This is exactly the greedy choice that minimizes cost.

This reduction, from tree construction to greedy removal of the smallest element, is what makes the problem tractable. Instead of exploring all possible tree structures (exponential), you just repeatedly remove the smallest adjacent element (linear with a stack).

The monotonic stack approach

Maintain a decreasing stack. Process each element in arr from left to right:

1. While the stack's top is smaller than or equal to the current element, pop it. The cost of removing that popped value is popped * min(stack_top, current). The popped element gets paired with its smaller neighbor, which is the greedy optimal choice.
2. Push the current element onto the stack.
3. After processing all elements, pop remaining elements from the stack and pair each with its neighbor (the new stack top).

Why does the decreasing stack work? It keeps track of the "active" maximums. When a value on top of the stack is smaller than the incoming value, that smaller value is sandwiched between two larger values. Its cheapest removal is guaranteed to be with the smaller of those two neighbors, which is exactly min(stack_top, current).

Step-by-step walkthrough

Let's trace through arr = [6, 2, 4] using the monotonic stack approach. The stack is shown at each step along with the running cost.

Notice the pattern:

• The stack stays decreasing. Whenever the incoming element is larger than the top, the top gets popped and paired.
• Each element is pushed once and popped once. That gives O(n) total work across the entire algorithm.
• The greedy choice is always correct. The smallest element gets paired with its smaller neighbor, minimizing the product. This is provably optimal because removing a small element early prevents it from being multiplied by a larger value later.

The code

def mctFromLeafValues(arr):
    stack = [float('inf')]
    cost = 0

    for val in arr:
        while stack[-1] <= val:
            popped = stack.pop()
            cost += popped * min(stack[-1], val)
        stack.append(val)

    while len(stack) > 2:
        cost += stack.pop() * stack[-1]

    return cost

Breaking it down:

1. Start with a sentinel value inf on the stack. This avoids empty-stack checks when computing min(stack_top, current).
2. For each value in arr, pop elements that are smaller than or equal to it. Each popped element costs popped * min(stack_top, current).
3. Push the current value.
4. After the main loop, pop remaining elements (except the sentinel). Each costs popped * stack_top, because there is no "current" element on the right anymore.
5. Return the accumulated cost.

The sentinel inf is a clean trick. It ensures the stack is never truly empty, so stack[-1] is always safe. And since inf is larger than any array value, it never gets popped during the main loop.

Complexity analysis

Time: O(n). Each of the n elements is pushed onto the stack exactly once and popped at most once. The while loop does at most n pops total across all iterations.

Space: O(n). In the worst case (a strictly decreasing array like [8, 6, 4, 2]), nothing gets popped during the main loop. The stack holds all n elements plus the sentinel.

The DP approach considers every way to split arr[i..j] into two halves, which is O(n^3) with memoization. The greedy scan approach repeatedly finds and removes the minimum, but finding the minimum each time is O(n). The monotonic stack does the same greedy removal in amortized O(1) per element.

The building blocks

This problem is built on two reusable bricks:

Monotonic stack pop loop

The core pattern is the same one from Daily Temperatures and Largest Rectangle in Histogram:

while stack and compare(current, stack[-1]):
    popped = stack.pop()
    # process popped element using current and stack[-1]
stack.append(current)

For this problem, the comparison is stack[-1] <= val (pop when the top is smaller than or equal to the current). The processing step computes popped * min(stack[-1], val). Same structure as every other monotonic stack problem, just a different computation on pop.

Greedy removal of the minimum

The insight that you should always remove the smallest adjacent element first is a general greedy principle. You see it in problems like Burst Balloons (remove elements in an order that minimizes total cost) and in interval scheduling. The monotonic stack is just the efficient data structure that implements this greedy removal in O(n).

Sentinel value to simplify edge cases

Using float('inf') as a sentinel at the bottom of the stack eliminates the need for empty-stack checks. This is a reusable trick whenever your stack-based algorithm needs to access stack[-1] after popping. You will see it in Largest Rectangle in Histogram (where some solutions append a 0-height bar at the end) and in other monotonic stack problems.

Edge cases

Before submitting, verify your solution handles:

• Two elements like [3, 5]: only one internal node. Cost = 3 * 5 = 15. The stack processes this in one pop during cleanup.
• All equal like [4, 4, 4, 4]: each pop produces cost = 4 * 4 = 16. Three internal nodes, total = 48.
• Strictly increasing like [1, 2, 3, 4]: each new element pops the previous one immediately. The smallest values get paired first, which is optimal.
• Strictly decreasing like [4, 3, 2, 1]: nothing gets popped during the main loop. The cleanup phase handles everything, pairing from the top of the stack downward.
• Single element [7]: no internal nodes needed. Cost = 0. The while loop and cleanup produce nothing.

The monotonic stack solution handles all of these without special-case code.

From understanding to recall

You have seen how the monotonic stack reduces tree construction to greedy pairing, and how the sentinel simplifies the code. The algorithm is elegant, but it has a few details that trip people up: the <= comparison (not <), the min(stack[-1], val) cost formula, and the cleanup phase that pairs remaining stack elements.

Under time pressure, it is easy to forget the sentinel, use the wrong comparison direction, or miss the cleanup. These are recall failures, not conceptual ones. You understand the algorithm, you just cannot reproduce it under stress.

Spaced repetition fixes this. You practice the pop loop, the sentinel setup, and the cleanup at increasing intervals. After a few reps, the code flows without hesitation. When you see a problem that asks you to minimize cost by removing or pairing adjacent elements, your hands know what to type.

Related posts

• Largest Rectangle in Histogram - Another monotonic stack problem where the pop loop computes a different quantity (area instead of pairing cost)
• Daily Temperatures - The gentlest introduction to the monotonic stack pop loop, computing distance to the next greater element
• Burst Balloons - A related "remove elements to minimize cost" problem solved with interval DP, showing the DP approach that the greedy stack replaces here

CodeBricks breaks the monotonic stack pattern into its reusable pieces and drills them individually. You type the pop loop, the sentinel trick, and the cleanup phase from scratch each time, building the muscle memory so that when you see Minimum Cost Tree From Leaf Values or any adjacent-pairing problem in an interview, the code flows without hesitation.