Minimum Cost Tree From Leaf Values - Video Solutions
Lecture 129: Minimum Cost Tree From Leaf Values || DP Series
Minimum Cost Tree From Leaf Values - Video Solution
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 37,810 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given an array arr of positive integers, consider all binary trees such that:
- Each node has either
0or2children; - The values of
arrcorrespond to the values of each leaf in an in-order traversal of the tree. - The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.
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] <= 15- It is guaranteed that the answer fits into a 32-bit signed integer (i.e., it is less than 231).
Approach Overview
Problem 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.
Complexity Analysis
| 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 |