Given a binary tree, find the sum of all parent-child differences for all the non-leaf nodes of the given binary tree.
Note that parent-child difference is (parent node’s value – (sum of child node’s values)).
Examples:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
Output: -23
1st parent-child difference = 1 -(2 + 3) = -4
2nd parent-child difference = 2 -(4 + 5) = -7
3rd parent-child difference = 3 -(6 + 7) = -10
4th parent-child difference = 6 - 8 = -2
Total sum = -23
Input:
1
/ \
2 3
\ /
5 6
Output: -10
Naive Approach: The idea is to traverse the tree in any fashion and check if the node is the leaf node or not. If the node is non-leaf node, add (node data – sum of children node data) to result.
Efficient Approach: In the final result, a close analysis suggests that each internal node ( nodes which are neither root nor leaf) once gets treated as a child and once as a parent hence their contribution in the final result is zero. Also, the root is only treated as a parent once and in a similar fashion, all leaf nodes are treated as children once. Hence, the final result is (value of root – sum of all leaf nodes).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure for a binary tree nodestruct Node { int data; Node *left, *right;};// Returns a new nodeNode* newNode(int data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL;}// Utility function which calculates// the sum of all leaf nodesvoid leafSumFunc(Node* root, int* leafSum){ if (!root) return; // Add root data to sum if // root is a leaf node if (!root->left && !root->right) *leafSum += root->data; // Recursively check in the left // and the right sub-tree leafSumFunc(root->left, leafSum); leafSumFunc(root->right, leafSum);}// Function to return the required resultint sumParentChildDiff(Node* root){ // If root is null if (!root) return 0; // If only node is the root node if (!root->left && !root->right) return root->data; // Find the sum of all the leaf nodes int leafSum = 0; leafSumFunc(root, &leafSum); // Root - sum of all the leaf nodes return (root->data - leafSum);}// Driver codeint main(){ // Construct binary tree Node* root = newNode(1); root->left = newNode(2); root->left->left = newNode(4); root->left->right = newNode(5); root->right = newNode(3); root->right->right = newNode(7); root->right->left = newNode(6); cout << sumParentChildDiff(root); return 0;} |
Java
// Java implementation of the approachclass GFG{// Structure for a binary tree nodestatic class Node{ int data; Node left, right;};// Returns a new nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}static int leafSum;// Utility function which calculates// the sum of all leaf nodesstatic void leafSumFunc(Node root ){ if (root == null) return; // Add root data to sum if // root is a leaf node if (root.left == null && root.right == null) leafSum += root.data; // Recursively check in the left // and the right sub-tree leafSumFunc(root.left); leafSumFunc(root.right);}// Function to return the required resultstatic int sumParentChildDiff(Node root){ // If root is null if (root == null) return 0; // If only node is the root node if (root.left == null && root.right == null) return root.data; // Find the sum of all the leaf nodes leafSum = 0; leafSumFunc(root); // Root - sum of all the leaf nodes return (root.data - leafSum);}// Driver codepublic static void main(String args[]){ // Construct binary tree Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.right = newNode(7); root.right.left = newNode(6); System.out.println( sumParentChildDiff(root));}}// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach # Structure for a binary tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None# Utility function which calculates # the sum of all leaf nodes def leafSumFunc(root, leafSum): if not root: return 0 # Add root data to sum # if root is a leaf node if not root.left and not root.right: leafSum += root.data # Recursively check in the # left and the right sub-tree leafSum = max(leafSumFunc(root.left, leafSum), leafSum) leafSum = max(leafSumFunc(root.right, leafSum), leafSum) return leafSum# Function to return the required result def sumParentChildDiff(root): # If root is None if not root: return 0 # If only node is the root node if not root.left and not root.right: return root.data # Find the sum of all the leaf nodes leafSum = leafSumFunc(root, 0) # Root - sum of all the leaf nodes return root.data - leafSum # Driver code if __name__ == "__main__": # Construct binary tree root = Node(1) root.left = Node(2) root.left.left = Node(4) root.left.right = Node(5) root.right = Node(3) root.right.right = Node(7) root.right.left = Node(6) print(sumParentChildDiff(root)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System; class GFG{// Structure for a binary tree nodepublic class Node{ public int data; public Node left, right;};// Returns a new nodestatic Node newNode(int data){ Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp;}static int leafSum;// Utility function which calculates// the sum of all leaf nodesstatic void leafSumFunc(Node root ){ if (root == null) return; // Add root data to sum if // root is a leaf node if (root.left == null && root.right == null) leafSum += root.data; // Recursively check in the left // and the right sub-tree leafSumFunc(root.left); leafSumFunc(root.right);}// Function to return the required resultstatic int sumParentChildDiff(Node root){ // If root is null if (root == null) return 0; // If only node is the root node if (root.left == null && root.right == null) return root.data; // Find the sum of all the leaf nodes leafSum = 0; leafSumFunc(root); // Root - sum of all the leaf nodes return (root.data - leafSum);}// Driver codepublic static void Main(String []args){ // Construct binary tree Node root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.right = newNode(7); root.right.left = newNode(6); Console.WriteLine( sumParentChildDiff(root));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the approach // Structure for a binary tree node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Returns a new node function newNode(data) { let temp = new Node(data); return temp; } let leafSum; // Utility function which calculates // the sum of all leaf nodes function leafSumFunc(root) { if (root == null) return; // Add root data to sum if // root is a leaf node if (root.left == null && root.right == null) leafSum += root.data; // Recursively check in the left // and the right sub-tree leafSumFunc(root.left); leafSumFunc(root.right); } // Function to return the required result function sumParentChildDiff(root) { // If root is null if (root == null) return 0; // If only node is the root node if (root.left == null && root.right == null) return root.data; // Find the sum of all the leaf nodes leafSum = 0; leafSumFunc(root); // Root - sum of all the leaf nodes return (root.data - leafSum); } // Construct binary tree let root = newNode(1); root.left = newNode(2); root.left.left = newNode(4); root.left.right = newNode(5); root.right = newNode(3); root.right.right = newNode(7); root.right.left = newNode(6); document.write( sumParentChildDiff(root)); </script> |
Output:
-21
Time complexity: O(N) where N is no of nodes in given binary tree
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!
