1.
Introduction
2.
The Problem Statement
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
Complexity Analysis
4.
4.1.
What is a Binary Tree?
4.2.
What is a subtree?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

The Maximum Cost of Splitting Binary Tree into Two Halves

Ujjawal Gupta
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss a problem based on a Binary tree in which we are asked to find the maximum possible cost after splitting the binary tree into two halves. Problems based on binary trees are widely asked in competitive programming contests and various coding interviews. Here we will discuss the efficient approach to reach our result.

The Problem Statement

You are given a binary tree with ‘N’ node numbers from 0 to N -1 and ‘N - 1’ edges. You are also given an array ‘VALUE’ which contains the values of each node. Your task is to find the maximum cost of splitting the binary tree into two halves. The cost of splitting the binary tree equals the product of the sum of node values of both subtrees.

Explanation

Let’s understand the problem statement with the help of an example as shown below:

Here we are given a binary tree with six nodes and five edges, and the value array is {10, 20, 30, 40, 50, 60}. So the value of the 0th node is 10, 1st node is 20, the 2nd node is 30, the 3rd node is 40, the 4th node is 50, and the 5th node is 60. We need to find the maximum cost after splitting it into two parts. So, we need to check the cost after deleting a particular edge and take the maximum among them.

Cost after deleting an edge is defined as the Sum of values of each node in 1st subtree) * (Sum of values of each node in 2nd subtree).

In the above example, we will get the maximum cost after deleting the edge between 0->1 as the sum of values of the subtree with rooted ‘1’ is 20 + 40 + 50 = 110 and the sum of values of the subtree with rooted ‘0’ is 10 + 30 + 60 = 100. Hence cost is 110*100=11000, which is the maximum among all other cases.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

The most straightforward and most efficient approach is to traverse the given binary tree and, for each edge, find the cost after removing that edge, and after traversal, the maximum cost among all is our answer.

Algorithm

• Create a binary tree using an adjacency list.
• Create an array, SUM[] to store the sum of all nodes of the subtree rooted with the ith node.
• Create a variable ‘ANS’ to store the final answer.
• Create a getMaxCost() function for getting cost after removal of that particular edge.
• Call the getMaxCost() for all the nodes.
• Print the ‘ANS.’

Program

``````#include <iostream>
#include <vector>
using namespace std;

// Add an edge from v1 to v2.
void addEdge(vector<vector<int>> &tree, int v1, int v2)
{
tree[v1].push_back(v2);
tree[v2].push_back(v1);
}
// Globally declare 'n' number of nodes.
int n;

// Function to create binary tree.
vector<vector<int>> createBinaryTree()
{

// Input number of nodes in binary tree.
cin >> n;

// Creating tree vector to store edges.
vector<vector<int>> tree(n);
for (int i = 0; i < n - 1; i++)
{

// input v1,v2 i.e. edge from v1 to v2.
int v1, v2;
cin >> v1 >> v2;
}
// return binary tree.
return tree;
}

// Function to initialize the sum array to store the sum till nth node.
void setSum(vector<vector<int>> tree, vector<int> values, int sum[], int root, int parent)
{

// base condition in recursive call.
if (tree[root].size() == 0)
sum[root] = values[root];
else
{
for (int i = 0; i < tree[root].size(); i++)
{

// recursively call setSum function.
if (tree[root][i] != parent)
{
setSum(tree, values, sum, tree[root][i], root);
sum[root] += sum[tree[root][i]];
}
}
sum[root] += values[root];
}
}

// Function to get the Maximum cost.
void getMaxCost(int sum[], vector<vector<int>> tree, int root, int &ans)
{

// base condition in recursive call.
if (tree[root].size() == 0)
return;
for (int i = 0; i < tree[root].size(); i++)
{
ans = max(sum[tree[root][i]] * (sum[0] - sum[tree[root][i]]), ans);
}
}

int main()
{
vector<vector<int>> tree;

// call create binary tree function.
tree = createBinaryTree();
vector<int> values(n);
for (int i = 0; i < n; i++)
{
cin >> values[i];
}

// creating array sum to store sum.
int sum[n] = {0};
setSum(tree, values, sum, 0, -1);
int ans = 0;
for (int i = 0; i < n; i++)
getMaxCost(sum, tree, i, ans);

// cout<< maximum cost.
cout << ans;
return 0;
}``````

Input

``````6
0 1
0 2
1 3
1 4
2 5
10 20 30 40 50 60 ``````

Output

``11000``

Complexity Analysis

Time Complexity

O(N), where ‘N’ is the total number of nodes in the given binary tree.

Visiting each node of the tree takes O(N) time.

Space Complexity

O(N), where ‘N’ is the total number of nodes in the given binary tree.

Because creating an array ‘SUM’ of size ‘N’ takes O(N) space.

What is a Binary Tree?

A Binary Tree is a Tree of Data Structure in which each node can have a maximum of two children

What is a subtree?

A subtree for any node is the part of the tree that is present as its child as the root node. For example for a binary tree, each node can have two subtrees, left and right both of them have the nodes' left child and right child as root respectively.

Conclusion

This blog has taught us the most straightforward and efficient approach to solving the maximum cost of splitting binary trees into two halves. This problem is the variation of the tree traversal problem, so practice tree traversal questions before moving further.