The Maximum Cost of Splitting Binary Tree into Two Halves

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;
        addEdge(tree, 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;
}

You can also try this code with Online C++ Compiler

Run Code

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.

Frequently Asked Questions

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.

Recommended Reading:

• Boundary Traversal Of Binary Tree
• Maximum Spiral Sum in Binary Tree
• Maximum Average of Subtree Values in a Given Binary Tree
• Maximum Level Sum in an N-Ary Tree
• Maximum Width of a Binary Tree with a Null Value
• Find Maximum GCD Value From Root to Leaf in a Binary Tree

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Cheers!