Domain 2MediumMEDIUM

Minimum Cost Tree From Leaf Values

Uses Interval Dynamic Programming where dp[i][j] stores min cost for leaves i..j, merging adjacent subtrees with cost equal to product of max leaf values in each subtree.

Domain: medium•Updated: 2026-09-09
#dynamic_programming#interval_dp#o(n^4)#o(n^2)

Problem Breakdown

  • Inputs: An array arr containing positive integers (N≤40N \le 40).
  • Outputs: The minimum possible integer sum representing non-leaf nodes.
  • Constraints & Edge Cases:
    • Array length is at least 2, so a valid tree always exists (at least one merge needed).
    • Values are positive (1≤arr[i]≤151 \le arr[i] \le 15), ensuring no zero-cost merges or negative logic issues.
    • The result fits in a standard integer; Python handles arbitrary precision automatically to avoid overflow concerns during intermediate calculations.

Intuition

This problem asks us to find the optimal structure of a binary tree given fixed leaf values and an order constraint (in-order traversal).

  1. Brute Force: We could try every possible way to merge adjacent leaves into subtrees until one root remains. The number of such trees grows according to Catalan numbers (Cn−1C_{n-1}). For N=40N=40, this is computationally infeasible (exponential time complexity).
  2. Key Insight: This structure resembles the “Matrix Chain Multiplication” or Optimal Binary Search Tree problems, which are solved using Dynamic Programming on intervals. We want to partition the array into two sub-intervals at every step of merging subtrees.
  3. Optimization Strategy: To minimize the total cost (sum of products), we need to decide where to split each range [i..j][i..j] optimally. Since the constraints are small (N≤40N \le 40), an Interval DP approach is perfectly acceptable and easier to explain clearly than a Monotonic Stack solution, though the stack method offers better asymptotic complexity for larger inputs.

Approach

We will use Interval Dynamic Programming.

  1. Define dp[i][j] as the minimum cost to form a tree using leaves from index ii through jj.
  2. Initialize base cases: For any single leaf (i==ji == j), there are no internal nodes, so the cost is 0 (dp[i][i] = 0).
  3. Iterate over all possible lengths of subarrays len starting from 2 up to NN. This ensures we solve smaller intervals before larger ones (bottom-up).
  4. For each interval [i..j], iterate through every possible split point k.
    • Left child covers range [i, k].
    • Right child covers range [k+1, j].
  5. The cost for a specific split is:
    cost=dp[i][k]+dp[k+1][j]+(max⁡(arr[i..k])×max⁡(arr[k+1..j]))\text{cost} = \text{dp}[i][k] + \text{dp}[k+1][j] + (\max(\text{arr}[i..k]) \times \max(\text{arr}[k+1..j]))
  6. Store the minimum cost found across all k in dp[i][j].
  7. Finally, return dp[0][N-1].

Complexity Analysis

  • Time Complexity: O(N4)O(N^4) with naive slicing for max calculation inside loops (∑len(N−len)⋅len⋅O(len)\sum_{len} (N-len) \cdot len \cdot O(len)). However, given the strict constraint N≤40N \le 40, this is approximately 2.56×1062.56 \times 10^6 operations in worst case, which fits well within time limits for Python. An optimized version using a precomputed max table or sparse RMQ would reduce it to strictly O(N3)O(N^3).
  • Space Complexity: O(N2)O(N^2) due to the DP table storing results for all sub-intervals [i][j].

Solution

class Solution:
    def mctFromLeafValues(self, arr):
        n = len(arr)
        
        # dp[i][j] stores the minimum cost of tree formed by leaves from index i to j
        dp = [[0] * n for _ in range(n)]

        # Iterate over length of subarray (from 2 up to N)
        for length in range(2, n + 1):
            # Start index of the interval
            for i in range(n - length + 1):
                j = i + length - 1
                
                # Initialize with a large value; we want min cost
                dp[i][j] = float('inf')

                # Try every possible split point k between i and j-1
                # Left child: [i, k], Right child: [k+1, j]
                for k in range(i, j):
                    left_cost = dp[i][k]
                    right_cost = dp[k + 1][j]
                    
                    # Calculate max leaf values for the two subtrees. 
                    # With N <= 40, slicing is acceptable (O(N^3) to O(N^4)).
                    # For larger constraints, precompute range maximums or use a monotonic stack approach.
                    left_max = max(arr[i : k + 1])
                    right_max = max(arr[k + 1 : j + 1])
                    
                    current_cost = left_cost + right_cost + (left_max * right_max)
                    dp[i][j] = min(dp[i][j], current_cost)

        return dp[0][n - 1]

Edge Cases Handled

  • Minimum Array Length: The loop for length starts at 2. Since constraints guarantee N≥2N \ge 2, the base case of single leaves is implicitly handled by initialization (dp[i][i]=0).
  • Single Element Ranges: When calculating max values, if a range has only one element (e.g., left child [k+1]), max() correctly returns that value. The logic holds for the smallest valid tree size (N=2N=2).
  • Large Values/Overflow: Python integers automatically handle arbitrary precision. While constraints guarantee 32-bit fit, intermediate products could theoretically exceed standard integer limits in other languages; here it is handled safely without explicit checks needed given problem guarantees.