Minimum Cost Tree From Leaf Values - Practice Coding Problems

Minimum Cost Tree From Leaf Values - 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

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.

Input & Output

Example 1 — Basic Case

$ Input: arr = [6,2,4]

› Output: 32

💡 Note: There are two possible trees. The first has non-leaf node sum 36, the second has non-leaf node sum 32. Tree 1: ((6,2),4) → cost = 6*2 + max(6,2)*4 = 12 + 24 = 36. Tree 2: (6,(2,4)) → cost = 2*4 + 6*max(2,4) = 8 + 24 = 32.

Example 2 — Minimum Size

$ Input: arr = [4,11]

› Output: 44

💡 Note: Only one possible tree with root having value 4*11 = 44.

Example 3 — Multiple Elements

$ Input: arr = [1,2,3,4]

› Output: 28

💡 Note: Optimal grouping: (1,(2,(3,4))) → costs: 3*4=12, 2*4=8, 1*4=4, total=28.

Constraints

2 ≤ arr.length ≤ 40
1 ≤ arr[i] ≤ 15
It is guaranteed that the answer fits in a 32-bit signed integer (i.e., it is less than 2³¹)

Visualization

Tap to expand

Understanding the Visualization

Input

Array [6,2,4] representing leaf values in in-order traversal

Process

Build binary trees where internal nodes = product of max values from left and right subtrees

Output

Return minimum sum of all internal node values

Key Takeaway

🎯 Key Insight: Always remove smaller elements first using a monotonic stack to minimize total cost

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a greedy approach with a monotonic stack. Always remove smaller elements first to minimize the total cost. The optimal approach uses a stack in O(n) time, achieving much better performance than the O(n³) recursive solution. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(n³)	O(n²)	Try all possible ways to split the array and choose minimum cost
Greedy with Stack	O(n)	O(n)	Always remove the smallest element first to minimize cost

Recursive with Memoization — Algorithm Steps

Try every possible split point between elements
Recursively solve left and right subarrays
Combine results with cost = max(left) × max(right)
Use memoization to avoid recalculating same subarrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Array

Start with full array [6,2,4]

Try Splits

Try splitting at each position and calculate costs

Choose Minimum

Select the split with minimum total cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int getMax(int* arr, int start, int end) {
    int maxVal = arr[start];
    for (int i = start + 1; i <= end; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    return maxVal;
}

int dp(int* arr, int i, int j, int** memo, int n) {
    if (i >= j) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    
    int result = INT_MAX;
    
    for (int k = i; k < j; k++) {
        int leftCost = dp(arr, i, k, memo, n);
        int rightCost = dp(arr, k + 1, j, memo, n);
        int leftMax = getMax(arr, i, k);
        int rightMax = getMax(arr, k + 1, j);
        
        int totalCost = leftCost + rightCost + leftMax * rightMax;
        if (totalCost < result) result = totalCost;
    }
    
    memo[i][j] = result;
    return result;
}

int solution(int* arr, int n) {
    if (n <= 1) return 0;
    
    int** memo = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        memo[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            memo[i][j] = -1;
        }
    }
    
    int result = dp(arr, 0, n - 1, memo, n);
    
    for (int i = 0; i < n; i++) {
        free(memo[i]);
    }
    free(memo);
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[20], n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            arr[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(arr, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) subproblems, each taking O(n) time to find maximum values

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores results for all possible subarrays

⚠ Quadratic Space

89.0K Views

Medium Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler