Given a binary tree consisting of N nodes, the task is to split the binary tree into two subtrees by removing one edge such that the absolute difference of the sum of the subtrees is minimized.
Example:
Input: 1
/ \
2 3
/ \ \
4 5 8
/ \
6 7
Output: 6
Explanation: Split the tree between vertex 3 and 8. Subtrees created have sums 21 and 15Input: 1
/ \
2 3
/ \ / \
4 5 6 7
Output: 4
Explanation: Split the tree between vertex 1 and 3. Subtrees created have sums 16 and 12
Approach: Given problem can be solved by following the steps below:
- Initialize variable minDiff to maximum value of Integer which will store the answer
- Use postorder traversal to store the sum of current node, left subtree and right subtree in the current node
- Use preorder traversal and at every recursive call find the sum of subtrees if the split is between:
- current node and left child node
- current node and right child node
- Update minDiff if at any recursive call the difference of subtrees is less than minDiff
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;struct Node { Node* left; Node* right; int val; Node(int val) { this->val = val; this->left = nullptr; this->right = nullptr; }};int postOrder(Node* root){ if (root == nullptr) return 0; root->val += postOrder(root->left) + postOrder(root->right); return root->val;}void preOrder(Node* root, int minDiff[]){ if (root == nullptr) return; // Absolute difference in subtrees // if left edge is broken int leftDiff = abs(root->left->val - (root->val - root->left->val)); // Absolute difference in subtrees // if right edge is broken int rightDiff = abs(root->right->val - (root->val - root->right->val)); // Update minDiff if a difference // lesser than it is found minDiff[0] = min(minDiff[0], min(leftDiff, rightDiff)); return;}// Function to calculate minimum absolute// difference of subtrees after// splitting the tree into two partsint minAbsDiff(Node* root){ // Reference variable // to store the answer int minDiff[1]; minDiff[0] = INT_MAX; // Function to store sum of values // of current node, left subtree and // right subtree in place of // current node's value postOrder(root); // Function to perform every // possible split and calculate // absolute difference of subtrees preOrder(root, minDiff); return minDiff[0];}int main(){ // Construct the tree Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); // Print the output cout << minAbsDiff(root); return 0;}// This code is contributed by mukesh07. |
Java
// Java implementation for the above approachimport java.lang.Math;import java.io.*;class GFG { static class Node { Node left, right; int val; public Node(int val) { this.val = val; this.left = this.right = null; } } // Function to calculate minimum absolute // difference of subtrees after // splitting the tree into two parts public static int minAbsDiff(Node root) { // Reference variable // to store the answer int[] minDiff = new int[1]; minDiff[0] = Integer.MAX_VALUE; // Function to store sum of values // of current node, left subtree and // right subtree in place of // current node's value postOrder(root); // Function to perform every // possible split and calculate // absolute difference of subtrees preOrder(root, minDiff); return minDiff[0]; } public static int postOrder(Node root) { if (root == null) return 0; root.val += postOrder(root.left) + postOrder(root.right); return root.val; } public static void preOrder(Node root, int[] minDiff) { if (root == null) return; // Absolute difference in subtrees // if left edge is broken int leftDiff = Math.abs(root.left.val - (root.val - root.left.val)); // Absolute difference in subtrees // if right edge is broken int rightDiff = Math.abs(root.right.val - (root.val - root.right.val)); // Update minDiff if a difference // lesser than it is found minDiff[0] = Math.min(minDiff[0], Math.min(leftDiff, rightDiff)); return; } // Driver code public static void main(String[] args) { // Construct the tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); // Print the output System.out.println(minAbsDiff(root)); }} |
Python3
# Python3 implementation for the above approachimport sys# Structure of Nodeclass Node: def __init__(self, val): self.val = val self.left = None self.right = None# Function to calculate minimum absolute# difference of subtrees after# splitting the tree into two partsdef minAbsDiff(root): # Reference variable # to store the answer minDiff = [0]*(1) minDiff[0] = sys.maxsize # Function to store sum of values # of current node, left subtree and # right subtree in place of # current node's value postOrder(root) # Function to perform every # possible split and calculate # absolute difference of subtrees preOrder(root, minDiff) return minDiff[0]def postOrder(root): if (root == None): return 0 root.val += postOrder(root.left) + postOrder(root.right) return root.valdef preOrder(root, minDiff): if (root == None): return # Absolute difference in subtrees # if left edge is broken leftDiff = abs(root.left.val - (root.val - root.left.val)) # Absolute difference in subtrees # if right edge is broken rightDiff = abs(root.right.val - (root.val - root.right.val)) # Update minDiff if a difference # lesser than it is found minDiff[0] = min(minDiff[0], min(leftDiff, rightDiff)) return# Construct the treeroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.left = Node(6)root.right.right = Node(7)# Print the outputprint(minAbsDiff(root))# This code is contributed by rameshtravel07. |
C#
// C# implementation for the above approachusing System;public class GFG { class Node { public Node left, right; public int val; } static Node newNode(int data) { Node newNode = new Node(); newNode.val = data; newNode.left= null; newNode.right = null; return newNode; } // Function to calculate minimum absolute // difference of subtrees after // splitting the tree into two parts static int minAbsDiff(Node root) { // Reference variable // to store the answer int[] minDiff = new int[1]; minDiff[0] = Int32.MaxValue; // Function to store sum of values // of current node, left subtree and // right subtree in place of // current node's value postOrder(root); // Function to perform every // possible split and calculate // absolute difference of subtrees preOrder(root, minDiff); return minDiff[0]; } static int postOrder(Node root) { if (root == null) return 0; root.val += postOrder(root.left) + postOrder(root.right); return root.val; } static void preOrder(Node root, int[] minDiff) { if (root == null) return; // Absolute difference in subtrees // if left edge is broken int leftDiff = Math.Abs(root.left.val - (root.val - root.left.val)); // Absolute difference in subtrees // if right edge is broken int rightDiff = Math.Abs(root.right.val - (root.val - root.right.val)); // Update minDiff if a difference // lesser than it is found minDiff[0] = Math.Min(minDiff[0], Math.Min(leftDiff, rightDiff)); return; } // Driver code public static void Main() { // Construct the tree Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); // Print the output Console.Write(minAbsDiff(root)); }}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // Javascript implementation for the above approach // Structure of Node class Node { constructor(val) { this.left = null; this.right = null; this.val = val; } } // Function to calculate minimum absolute // difference of subtrees after // splitting the tree into two parts function minAbsDiff(root) { // Reference variable // to store the answer let minDiff = new Array(1); minDiff[0] = Number.MAX_VALUE; // Function to store sum of values // of current node, left subtree and // right subtree in place of // current node's value postOrder(root); // Function to perform every // possible split and calculate // absolute difference of subtrees preOrder(root, minDiff); return minDiff[0]; } function postOrder(root) { if (root == null) return 0; root.val += postOrder(root.left) + postOrder(root.right); return root.val; } function preOrder(root, minDiff) { if (root == null) return; // Absolute difference in subtrees // if left edge is broken let leftDiff = Math.abs(root.left.val - (root.val - root.left.val)); // Absolute difference in subtrees // if right edge is broken let rightDiff = Math.abs(root.right.val - (root.val - root.right.val)); // Update minDiff if a difference // lesser than it is found minDiff[0] = Math.min(minDiff[0], Math.min(leftDiff, rightDiff)); return; } // Construct the tree let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); // Print the output document.write(minAbsDiff(root));// This code is contributed by decode2207.</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
