Watch 10 video solutions for Minimum Cost Tree From Leaf Values, a medium level problem involving Array, Dynamic Programming, Stack. This walkthrough by CodeHelp - by Babbar has 36,443 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array arr of positive integers, consider all binary trees such that:
0 or 2 children;arr correspond to the values of each leaf in an in-order traversal of the tree.Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
A node is a leaf if and only if it has zero children.
Example 1:
Input: arr = [6,2,4] Output: 32 Explanation: There are two possible trees shown. The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.
Example 2:
Input: arr = [4,11] Output: 44
Constraints:
2 <= arr.length <= 401 <= arr[i] <= 15Problem Overview: You are given an array where each value represents a leaf node in an in-order traversal of a binary tree. Every non-leaf node value equals the product of the maximum leaf values in its left and right subtrees. The task is to construct the tree with the minimum possible sum of all non-leaf node values.
Approach 1: Dynamic Programming (O(n³) time, O(n²) space)
This approach treats the problem similarly to matrix chain multiplication. Use a DP table dp[i][j] representing the minimum cost to build a tree from subarray arr[i..j]. For each range, try every possible partition k between i and j. The cost equals dp[i][k] + dp[k+1][j] + max(arr[i..k]) * max(arr[k+1..j]). Precompute maximum values for subarrays to avoid repeated scans. This solution demonstrates the optimal substructure clearly but becomes slow for larger inputs due to the cubic time complexity. Useful when learning interval dynamic programming patterns.
Approach 2: Greedy Monotonic Stack (O(n) time, O(n) space)
The optimal insight is that smaller leaves should be combined earlier to minimize multiplication cost. Use a decreasing monotonic stack. Iterate through the array and maintain elements in decreasing order. When the current value is greater than or equal to the stack top, pop the top element and add the cost mid * min(stackTop, current). This ensures each leaf pairs with the smallest possible larger neighbor, minimizing contribution to the total sum. After processing the array, multiply remaining adjacent stack elements until one element remains. The stack guarantees each element is pushed and popped once, giving linear complexity. This pattern frequently appears in problems involving nearest greater elements and stack-based greedy optimization.
Recommended for interviews: Start by explaining the dynamic programming formulation to show you understand the optimal substructure of the problem. Then move to the greedy monotonic stack solution, which reduces the complexity from O(n³) to O(n). Interviewers typically expect the stack-based approach because it demonstrates pattern recognition and optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Interval DP) | O(n³) | O(n²) | When demonstrating interval DP reasoning or solving small input sizes |
| Greedy Monotonic Stack | O(n) | O(n) | Best choice for interviews and production due to linear performance |