Problem Description

The Minimum Cost Tree From Leaf Values problem asks you to build a binary tree from an array of positive integers arr, where each value in arr represents a leaf node in an in-order traversal. Each non-leaf node's value is equal to the product of the largest leaf values in its left and right subtrees. The cost of the tree is the sum of all non-leaf node values. Your goal is to construct the tree with the minimum possible total cost.

• Each element in arr must be used exactly once as a leaf node.
• The tree must be a full binary tree (every node has 0 or 2 children).
• There is only one valid solution that yields the minimum cost.
• You cannot reuse or rearrange elements in arr.

Thought Process

At first glance, one might consider generating every possible binary tree structure and calculating the cost for each. However, this brute-force approach is highly inefficient, as the number of possible binary trees grows exponentially with the number of leaves.

The challenge is to combine leaves in a way that minimizes the sum of the products of the largest leaves in each subtree. Since the cost comes from multiplying two leaves, and larger numbers produce higher products, it is wise to pair smaller numbers early to avoid large intermediate products.

This leads to thinking about greedy or dynamic programming strategies: Is there a local choice that always leads to a globally optimal solution? By simulating combinations, we can try to always combine the smallest adjacent leaves first.

Solution Approach

The most efficient solution uses a monotonic stack to greedily combine the smallest adjacent leaves first, minimizing the cost at each step. Here’s how it works:

1. Initialize a stack: Start with an empty stack and a variable to keep track of the total cost.
2. Iterate through arr: For each value in arr:
   • While the stack is not empty and the top of the stack is less than or equal to the current value, pop the stack. This popped value is a candidate for combination.
   • Calculate the cost of combining the popped value with the smaller of its two neighbors (either the new top of the stack or the current value), and add this to the total cost.
   • Push the current value onto the stack.
3. Finish processing the stack: After iterating through arr, there may be values left on the stack. For each remaining pair, combine them and add the product to the total cost.

Why a stack? The stack helps keep track of the sequence of leaves, and allows us to efficiently find and combine the smallest adjacent values first, which is the key to minimizing the cost.

• This approach is much more efficient than brute-force or DP, running in linear time.

Example Walkthrough

Let's walk through an example with arr = [6, 2, 4]:

1. Start with an empty stack and total cost = 0.
2. Push 6 onto the stack: [6]
3. Next, 2: 2 < 6, so push 2: [6, 2]
4. Next, 4: 4 > 2, so pop 2. The next top is 6. Combine 2 with min(6, 4) = 4. Add 2*4=8 to total cost (now 8). Stack: [6]
5. Now, 4 < 6, so push 4: [6, 4]
6. End of array. Now combine remaining stack: pop 4, combine with 6: 6*4=24. Add to total cost (now 32).
7. Stack is now [6], done.

Result: The minimum cost is 32.

Time and Space Complexity

• Brute-force approach: Tries every possible binary tree structure. Time complexity is exponential, specifically O(C_n-1), where C_n-1 is the (n-1)th Catalan number. Space is also exponential due to recursion stack and tree storage.
• Monotonic stack approach: Each element is pushed and popped at most once, so time complexity is O(n). Space complexity is O(n) for the stack.

The stack-based greedy method is optimal for both time and space.

Summary

The Minimum Cost Tree From Leaf Values problem can be solved efficiently by greedily combining the smallest adjacent leaves first using a monotonic stack. This approach avoids the combinatorial explosion of brute-force methods and leverages the insight that pairing smaller values early prevents large products later. The stack-based algorithm is simple, elegant, and runs in linear time, making it ideal for large inputs.

Code Implementation

class Solution:
    def mctFromLeafValues(self, arr):
        stack = []
        res = 0
        for num in arr:
            while stack and stack[-1] <= num:
                mid = stack.pop()
                if stack:
                    res += mid * min(stack[-1], num)
                else:
                    res += mid * num
            stack.append(num)
        while len(stack) > 1:
            res += stack.pop() * stack[-1]
        return res
      

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        vector<int> stack;
        int res = 0;
        for (int num : arr) {
            while (!stack.empty() && stack.back() <= num) {
                int mid = stack.back();
                stack.pop_back();
                if (!stack.empty())
                    res += mid * min(stack.back(), num);
                else
                    res += mid * num;
            }
            stack.push_back(num);
        }
        while (stack.size() > 1) {
            int top = stack.back(); stack.pop_back();
            res += top * stack.back();
        }
        return res;
    }
};
      

class Solution {
    public int mctFromLeafValues(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int num : arr) {
            while (!stack.isEmpty() && stack.peek() <= num) {
                int mid = stack.pop();
                if (!stack.isEmpty()) {
                    res += mid * Math.min(stack.peek(), num);
                } else {
                    res += mid * num;
                }
            }
            stack.push(num);
        }
        while (stack.size() > 1) {
            res += stack.pop() * stack.peek();
        }
        return res;
    }
}
      

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