# Minimum Cost Tree From Leaf Values
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-tree-from-leaf-values
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe), [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## Problem
Given an array `arr` of positive integers, consider all binary trees such that:

* Each node has either `0` or `2` children;
* The values of `arr` correspond 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:**

![](https://assets.glich.co/dsa/minimum-cost-tree-from-leaf-values/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-cost-tree-from-leaf-values/image1.jpg) 

**Input:** arr = [4,11]
**Output:** 44

**Constraints:**

* `2 <= arr.length <= 40`
* `1 <= arr[i] <= 15`
* It is guaranteed that the answer fits into a **32-bit** signed integer (i.e., it is less than 231).

# Approaches
## Dynamic Programming
This approach uses dynamic programming, a standard technique for problems with optimal substructure and overlapping subproblems. We define a function `dp(i, j)` that computes the minimum cost to build a tree for the subarray `arr[i...j]`. The final answer is `dp(0, n-1)`.
**Time:** O(n^3) - There are three nested loops. The outer two loops iterate over all possible subarrays `(i, j)`, which is O(n^2). The inner loop iterates over all possible split points `k`, which takes O(n) time. This results in a total time complexity of O(n^3). · **Space:** O(n^2) - We use two 2D arrays, `dp` and `maxVal`, both of size n x n.
**Pros:** Conceptually straightforward and follows a standard DP pattern similar to Matrix Chain Multiplication.; Guaranteed to find the optimal solution by exploring all possibilities systematically.
**Cons:** The cubic time complexity makes it slow for larger constraints, although it passes for N <= 40.; Requires quadratic space, which can be memory-intensive.
### Explanation
The core idea is to try every possible split point `k` for a given subarray `arr[i...j]`. A split at `k` divides the subarray into two parts: `arr[i...k]` and `arr[k+1...j]`. These form the left and right subtrees of a new root node. The value of this new non-leaf node is the product of the largest leaf in its left subtree (`max(arr[i...k])`) and the largest leaf in its right subtree (`max(arr[k+1...j])`). The total cost for this particular split is the sum of the costs of the subproblems (`dp(i, k)` and `dp(k+1, j)`) plus the cost of the new root. We take the minimum cost over all possible split points `k`.

The recurrence relation is:
`dp(i, j) = min_{i <= k < j} (dp(i, k) + dp(k+1, j) + max(arr[i...k]) * max(arr[k+1...j]))`

The base case is `dp(i, i) = 0`, as a single leaf node is a tree with no non-leaf nodes and thus zero cost. We can implement this using a bottom-up approach, iterating through subarray lengths from 2 to `n`. To avoid recomputing maximums in subarrays repeatedly, we can precompute them in an auxiliary 2D array.

```java
class Solution {
    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        int[][] maxVal = new int[n][n];

        for (int i = 0; i < n; i++) {
            maxVal[i][i] = arr[i];
            for (int j = i + 1; j < n; j++) {
                maxVal[i][j] = Math.max(maxVal[i][j - 1], arr[j]);
            }
        }

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + maxVal[i][k] * maxVal[k + 1][j];
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }
        return dp[0][n - 1];
    }
}
```
### Algorithm
1. Let `n` be the length of `arr`.
2. Create a 2D array `dp[n][n]` to store the minimum cost for building a tree from the subarray `arr[i...j]`.
3. Create a 2D array `maxVal[n][n]` to store the maximum leaf value in `arr[i...j]`. Precompute this for efficiency.
4. Iterate over the length of the subarray, `len`, from 2 to `n`.
5. For each `len`, iterate over the starting index `i` from 0 to `n-len`.
6. The ending index `j` will be `i + len - 1`.
7. Initialize `dp[i][j]` to `Integer.MAX_VALUE`.
8. Iterate through all possible split points `k` from `i` to `j-1`.
9. Calculate the cost for the split at `k`: `cost = dp[i][k] + dp[k+1][j] + maxVal[i][k] * maxVal[k+1][j]`.
10. Update `dp[i][j] = min(dp[i][j], cost)`.
11. The final answer is `dp[0][n-1]`.

## Greedy Approach with List Simulation
This approach is based on a greedy insight. The problem can be rephrased as: repeatedly find a pair of adjacent numbers in a list, calculate their product, add it to the total cost, and replace the pair with their maximum. The greedy strategy is to always find the smallest number in the current list and combine it with its smaller neighbor to minimize the cost contribution at each step.
**Time:** O(n^2) - The process is repeated `n-1` times. In each iteration, finding the minimum element takes O(n) time, and removing an element from an `ArrayList` can also take O(n) time in the worst case. · **Space:** O(n) - We use a list to store the numbers, which takes space proportional to the input size.
**Pros:** More efficient than the O(n^3) DP approach.; The greedy logic is relatively easy to understand.
**Cons:** The simulation using a standard list (like Java's `ArrayList`) is inefficient. Finding the minimum and removing an element both take O(n) time, leading to a quadratic overall complexity.
### Explanation
The key observation is that each number `arr[i]` (except for the overall maximum in the array) must eventually be the smaller element in a product pair, effectively being 'removed' from the list of potential maximums. To minimize its contribution `arr[i] * partner`, we should choose the smallest possible `partner`. The best partners are its immediate neighbors in the current sequence.

The greedy strategy is to find the smallest element in the current list of numbers, say `x`. `x` is then paired with the smaller of its two adjacent neighbors. This operation corresponds to forming a new non-leaf node. We simulate this process by starting with a list of all numbers from `arr`. In each step, we find the minimum element, calculate the cost, add this cost to our total, and remove the minimum element from the list. This is repeated `n-1` times until only one element remains.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int mctFromLeafValues(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        int res = 0;
        while (list.size() > 1) {
            int minVal = Integer.MAX_VALUE;
            int minIdx = -1;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) < minVal) {
                    minVal = list.get(i);
                    minIdx = i;
                }
            }
            
            int leftNeighbor = (minIdx > 0) ? list.get(minIdx - 1) : Integer.MAX_VALUE;
            int rightNeighbor = (minIdx < list.size() - 1) ? list.get(minIdx + 1) : Integer.MAX_VALUE;
            
            res += minVal * Math.min(leftNeighbor, rightNeighbor);
            list.remove(minIdx);
        }
        return res;
    }
}
```
### Algorithm
1. Convert the input array `arr` into a `List` for easier element removal.
2. Initialize a variable `totalCost` to 0.
3. Loop `n-1` times, as we need to perform `n-1` combinations to form the final tree:
    a. Find the index `minIdx` of the minimum value in the current list.
    b. Determine the cost. If `minIdx` is at a boundary, the cost is the product of the minimum value and its single neighbor. Otherwise, it's the product of the minimum value and the smaller of its two neighbors.
    c. Add this cost to `totalCost`.
    d. Remove the element at `minIdx` from the list.
4. Return `totalCost`.

## Greedy Approach with Monotonic Stack
This is the most optimal approach, which implements the greedy strategy in linear time using a monotonic stack. The core idea is that when an element `arr[i]` is chosen to be a smaller part of a product, it's paired with the nearest greater element on its left or right. A monotonic stack is the perfect data structure to find these elements efficiently.
**Time:** O(n) - Each element from the input array `arr` is pushed onto the stack exactly once and popped from the stack at most once. Therefore, the overall time complexity is linear. · **Space:** O(n) - In the worst-case scenario (e.g., a decreasingly sorted array), the stack can hold all `n` elements.
**Pros:** Optimal O(n) time complexity.; Efficient O(n) space complexity.; Provides an elegant and concise solution to the problem.
**Cons:** The logic, especially the connection between the monotonic stack and the greedy choice, can be less intuitive to derive compared to the DP approach.
### Explanation
We maintain a monotonically decreasing stack. The stack stores leaf values that are candidates for being the larger value in a future product. We iterate through the input array `arr`. For each number `x`, we compare it with the top of the stack.

If `x` is greater than the stack's top element, it means `x` is the first greater element to the right for the element at the top of the stack. We pop elements from the stack as long as they are smaller than or equal to `x`. For each popped element `mid`, we calculate its contribution to the cost. The partners for `mid` are `x` (its nearest greater element on the right) and the new stack top (its nearest greater element on the left, due to the stack's decreasing nature). We multiply `mid` by the smaller of these two partners and add it to the total cost.

After this, we push `x` onto the stack to maintain the decreasing order. After iterating through the entire array, any remaining elements in the stack form a decreasing sequence. We process them by repeatedly pairing adjacent elements until only one is left.

```java
import java.util.Stack;

class Solution {
    public int mctFromLeafValues(int[] arr) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(Integer.MAX_VALUE); // Sentinel value

        for (int num : arr) {
            while (stack.peek() <= num) {
                int mid = stack.pop();
                res += mid * Math.min(stack.peek(), num);
            }
            stack.push(num);
        }

        while (stack.size() > 2) {
            res += stack.pop() * stack.peek();
        }
        
        return res;
    }
}
```
### Algorithm
1. Initialize `totalCost = 0` and an empty stack.
2. To simplify boundary conditions, push a sentinel value like `Integer.MAX_VALUE` onto the stack first.
3. Iterate through each number `num` in the input array `arr`.
4. While the element at the top of the stack is less than or equal to the current number `num`:
    a. Pop the top element, let's call it `mid`.
    b. `mid` is now paired up. Its right partner is `num`. Its left partner is the new top of the stack.
    c. Add the cost `mid * min(stack.peek(), num)` to `totalCost`.
5. Push the current number `num` onto the stack. This maintains the monotonically decreasing property of the stack.
6. After iterating through the entire array, the stack will contain a decreasing sequence of numbers (plus the sentinel). These are the largest leaf values of subtrees that haven't been merged yet.
7. While the stack has more than two elements (the last element and the sentinel), pop the top element and multiply it by the new top, adding the result to `totalCost`.
8. Return `totalCost`.

# Solutions
### Java

```java
class Solution { private Integer [][] f ; private int [][] g ; public int mctFromLeafValues ( int [] arr ) { int n = arr . length ; f = new Integer [ n ][ n ]; g = new int [ n ][ n ]; for ( int i = n - 1 ; i >= 0 ; -- i ) { g [ i ][ i ] = arr [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { g [ i ][ j ] = Math . max ( g [ i ][ j - 1 ], arr [ j ]); } } return dfs ( 0 , n - 1 ); } private int dfs ( int i , int j ) { if ( i == j ) { return 0 ; } if ( f [ i ][ j ] != null ) { return f [ i ][ j ]; } int ans = 1 << 30 ; for ( int k = i ; k < j ; k ++) { ans = Math . min ( ans , dfs ( i , k ) + dfs ( k + 1 , j ) + g [ i ][ k ] * g [ k + 1 ][ j ]); } return f [ i ][ j ] = ans ; } }
```

### CPP

```cpp
class Solution { public: int mctFromLeafValues ( vector < int >& arr ) { int n = arr . size (); int f [ n ][ n ]; int g [ n ][ n ]; memset ( f , 0 , sizeof ( f )); for ( int i = n - 1 ; ~ i ; -- i ) { g [ i ][ i ] = arr [ i ]; for ( int j = i + 1 ; j < n ; ++ j ) { g [ i ][ j ] = max ( g [ i ][ j - 1 ], arr [ j ]); } } function < int ( int , int ) > dfs = [ & ]( int i , int j ) -> int { if ( i == j ) { return 0 ; } if ( f [ i ][ j ] > 0 ) { return f [ i ][ j ]; } int ans = 1 << 30 ; for ( int k = i ; k < j ; ++ k ) { ans = min ( ans , dfs ( i , k ) + dfs ( k + 1 , j ) + g [ i ][ k ] * g [ k + 1 ][ j ]); } return f [ i ][ j ] = ans ; }; return dfs ( 0 , n - 1 ); } };
```

### Python

```python
class Solution : def mctFromLeafValues ( self , arr : List [ int ]) -> int : @ cache def dfs ( i : int , j : int ) -> Tuple : if i == j : return 0 , arr [ i ] s , mx = inf , - 1 for k in range ( i , j ): s1 , mx1 = dfs ( i , k ) s2 , mx2 = dfs ( k + 1 , j ) t = s1 + s2 + mx1 * mx2 if s > t : s = t mx = max ( mx1 , mx2 ) return s , mx return dfs ( 0 , len ( arr ) - 1 )[ 0 ]
```