We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost Tree From Leaf Values

Number: 1228

Difficulty: Medium

Paid? No

Companies: Google, MathWorks

Problem Description

Given an array of positive integers, the task is to build a binary tree where every non-leaf node has exactly two children and its value is equal to the product of the largest leaf value in its left subtree and the largest leaf value in its right subtree. The leaves of the tree, when read in an in-order fashion, are exactly the values of the input array. Among all possible binary trees satisfying these properties, return the minimum possible sum of the values of all non-leaf nodes.

Key Insights

  • The in-order property of leaves implies that the relative order of the array elements remains unchanged.
  • Each operation of combining two adjacent values produces a non-leaf node.
  • A greedy strategy can be applied: combining two numbers with smaller values first can potentially lower the overall cost.
  • A monotonic stack can be used to determine the optimal pairings; essentially, for each element you maintain a decreasing order in the stack to decide which element to combine.
  • The problem is similar in nature to matrix chain multiplication, but the greedy approach with a stack is both efficient and intuitive.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements, since each element is pushed and popped from the stack at most once. Space Complexity: O(n), for the stack used in the algorithm.

Solution

We use a greedy approach with a monotonic decreasing stack. The strategy works as follows:

  1. Initialize a stack with an infinitely large sentinel value.
  2. Iterate over each element in the array. For the current element, while the top of the stack is less than or equal to the current element, pop the stack and add to the result the product of the popped element and the minimum of the current element and the new top of the stack.
  3. Push the current element onto the stack.
  4. Once all array elements have been processed, combine the remaining elements in the stack from top to bottom.
  5. The accumulated result will be the minimum possible cost of all non-leaf nodes.

This method ensures that at each step, the combination is made in such a way that it minimizes the cost contribution of the smaller of the two numbers.

Code Solutions

# Python solution using a monotonic stack approach
class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # Initialize the result and the stack with a value of infinity
        res = 0
        stack = [float('inf')]
        # Iterate over each number in the input array
        for num in arr:
            # While the current number is greater than or equal to the top of the stack,
            # pop from the stack and add the cost of forming a non-leaf node.
            while stack and stack[-1] <= num:
                mid = stack.pop()
                res += mid * min(stack[-1], num)
            # Push the current number into the stack
            stack.append(num)
        # Final cost: combine the remaining elements in the stack
        while len(stack) > 2:
            res += stack.pop() * stack[-1]
        return res
← Back to All Questions