Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1228. Minimum Cost Tree From Leaf Values

My accepted Python solution to LeetCode problem 1228, Minimum Cost Tree From Leaf Values, running in 0ms.

  • Difficulty: Medium
  • Python
  • Runtime 0ms
  • Memory 17.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 0ms, memory 17.2MB, accepted 2026-01-02.

python
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # Greedy approach with monotonic stack
        # We want to combine smaller values first
        stack = [float('inf')]
        result = 0
        
        for num in arr:
            while stack[-1] <= num:
                mid = stack.pop()
                result += mid * min(stack[-1], num)
            stack.append(num)
        
        # Combine remaining elements in stack
        while len(stack) > 2:
            result += stack.pop() * stack[-1]
        
        return result

Source