Generate Complete Binary Tree in such a way that sum of non-leaf nodes is minimum
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> |
21
Time Complexity: O(n)
Auxiliary Space: O(n), where n is the length of the given array.
Contact Us