Generate Complete Binary Tree in such a way that sum of non-leaf nodes is minimum

0 0 5 minutes read

Given an array arr[] of size N, the task is to generate a Complete Binary Tree in such a way that sum of the non-leaf nodes is minimum, whereas values of the leaf node corresponds to the array elements in an In-order Traversal of the tree and value of each non-leaf node corresponds to the product of the largest leaf value in the left sub-tree and right sub-tree
Examples:

Input: arr[] = {1, 2, 3, 4}
Output: 20
Explanation:
Please refer below for explanation
Input: arr[] = {5, 2, 3}
Output: 21

Approach:
To remove a number arr[i], it needs a cost a * b, where b >= a and also an element of the array. To minimize the cost of removal, the idea is to minimize b. To compute the non-leaf node there are two candidates, that is the first largest number on the left and the first largest number on the right. The cost to remove arr[i] is a * min(left, right). It can be further decomposed as to find the next greater element in the array, on the left and one right.
Refer: Next greater element
Below is the implementation of the above approach:

C++

// C++ implementation to find the
// minimum cost tree
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum cost tree
int MinCostTree(int arr[], int n)
{
    int ans = 0;
 
    // Stack
    vector<int> st = { INT_MAX };
 
    // Loop to traverse the array elements
    for (int i = 0; i < n; i++) {
         
        // Keep array elements 
        // in decreasing order by popping out
        // the elements from stack till the top
        // element is less than current element
        while (st.back() <= arr[i]) {
             
            // Get top element
            int x = st.back();
 
            // Remove it
            st.pop_back();
 
            // Get the minimum cost to remove x
            ans += x * min(st.back(), arr[i]);
        }
 
        // Push current element
        st.push_back(arr[i]);
    }
 
    // Find cost for all remaining elements
    for (int i = 2; i < st.size(); i++)
        ans += st[i] * st[i - 1];
 
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 2, 3 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << MinCostTree(arr, n);
 
    return 0;
}

Java

// Java implementation to find the
// minimum cost tree
import java.util.*;
 
class GFG{
 
// Function to find minimum cost tree
static int MinCostTree(int arr[], int n)
{
    int ans = 0;
 
    // Stack
    Vector<Integer> st = new Vector<Integer>();
    st.add(Integer.MAX_VALUE);
 
    // Loop to traverse the array elements
    for (int i = 0; i < n; i++) {
         
        // Keep array elements 
        // in decreasing order by popping out
        // the elements from stack till the top
        // element is less than current element
        while (st.get(st.size()-1) <= arr[i]) {
             
            // Get top element
            int x = st.get(st.size()-1);
 
            // Remove it
            st.remove(st.size()-1);
 
            // Get the minimum cost to remove x
            ans += x * Math.min(st.get(st.size()-1), arr[i]);
        }
 
        // Push current element
        st.add(arr[i]);
    }
 
    // Find cost for all remaining elements
    for (int i = 2; i < st.size(); i++)
        ans += st.get(i) * st.get(i-1);
 
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 5, 2, 3 };
 
    int n = arr.length;
 
    // Function call
    System.out.print(MinCostTree(arr, n));
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 implementation to find the
# minimum cost tree
 
# Function to find minimum cost tree
def MinCostTree(arr, n):
     
    ans = 0
    st = [2**32]
     
    # Loop to traverse the array elements
    for i in range(n):
         
        # Keep array elements 
        # in decreasing order by popping out
        # the elements from stack till the top
        # element is less than current element
        while (st[-1] <= arr[i]):
             
            # Get top element
            x = st[-1]
             
            # Remove it
            st.pop()
             
            # Get the minimum cost to remove x
            ans += x * min(st[-1], arr[i])
             
        # Push current element
        st.append(arr[i])
         
    # Find cost for all remaining elements
    for i in range(2,len(st)):
        ans += st[i] * st[i - 1]
         
    return ans
     
# Driver Code
arr = [5, 2, 3]
 
n = len(arr)
 
# Function call
print(MinCostTree(arr, n))
 
# This code is contributed by shubhamsingh10

C#

// C# implementation to find the
// minimum cost tree
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find minimum cost tree
static int MinCostTree(int []arr, int n)
{
    int ans = 0;
 
    // Stack
    List<int> st = new List<int>();
    st.Add(int.MaxValue);
 
    // Loop to traverse the array elements
    for (int i = 0; i < n; i++) {
         
        // Keep array elements 
        // in decreasing order by popping out
        // the elements from stack till the top
        // element is less than current element
        while (st[st.Count-1] <= arr[i]) {
             
            // Get top element
            int x = st[st.Count-1];
 
            // Remove it
            st.RemoveAt(st.Count-1);
 
            // Get the minimum cost to remove x
            ans += x * Math.Min(st[st.Count-1], arr[i]);
        }
 
        // Push current element
        st.Add(arr[i]);
    }
 
    // Find cost for all remaining elements
    for (int i = 2; i < st.Count; i++)
        ans += st[i] * st[i-1];
 
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 5, 2, 3 };
 
    int n = arr.Length;
 
    // Function call
    Console.Write(MinCostTree(arr, n));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript implementation to find the
// minimum cost tree
 
// Function to find minimum cost tree
function MinCostTree(arr, n)
{
    let ans = 0;
 
    // Stack
    let st = new Array()
    st.push(Number.MAX_SAFE_INTEGER);
 
    // Loop to traverse the array elements
    for (let i = 0; i < n; i++) {
         
        // Keep array elements
        // in decreasing order by popping out
        // the elements from stack till the top
        // element is less than current element
        while (st[st.length -1] <= arr[i]) {
             
            // Get top element
            let x = st[st.length-1];
 
            // Remove it
            st.pop();
 
            // Get the minimum cost to remove x
            ans += x * Math.min(st[st.length - 1], arr[i]);
        }
 
        // Push current element
        st.push(arr[i]);
    }
 
    // Find cost for all remaining elements
    for (let i = 2; i < st.length; i++)
        ans += st[i] * st[i - 1];
 
    return ans;
}
 
// Driver Code
 
    let arr = [ 5, 2, 3 ];
 
    let n = arr.length;
 
    // Function call
    document.write(MinCostTree(arr, n));
 
    // This code is contributed by gfgking
</script>

Output:

Time Complexity: O(n)
Auxiliary Space: O(n), where n is the length of the given array.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!