Sum of all parent-child differences in a Binary Tree

0 0 6 minutes read

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 node
struct Node {
    int data;
    Node *left, *right;
};
 
// Returns a new node
Node* newNode(int data)
{
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
}
 
// Utility function which calculates
// the sum of all leaf nodes
void 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 result
int 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 code
int 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 approach
class GFG
{
 
// Structure for a binary tree node
static class Node
{
    int data;
    Node left, right;
};
 
// Returns a new node
static 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 nodes
static 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 result
static 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 code
public 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 approach
using System;
     
class GFG
{
 
// Structure for a binary tree node
public class Node
{
    public int data;
    public Node left, right;
};
 
// Returns a new node
static 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 nodes
static 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 result
static 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 code
public 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 zambiatek!