Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Sample Examples 
2.
Naive Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Efficient Approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently asked questions
4.1.
What is the difference between a binary tree and a binary search tree?
4.2.
What is inorder traversal ? 
4.3.
What is the difference between a full binary tree and a complete binary tree? 
4.4.
What is auxiliary space? 
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Sum of subtree depths for every node of a given binary tree

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

Introduction 

The problem states that we are given a binary tree, and we need to calculate the sum of subtree depths of a given binary tree. Refer to the given sample example to more clearly understand the problem statement. 

Binary Tree: As the name suggests, a binary tree is a tree in which every node can have at most two children, and they are known as the left and right children. 

Sample Examples 

 Input: Given The binary Tree

Output: The total sum of subtree depths is: 26

Explanation:

Let’s denote each subtree of this given binary tree, as 1A, 2A, 2B, 3A. 

Let’s Look at each subtree separately, in the given below figure. 

Let's denote each subtree of this given binary tree as 1A, 2A, 2B, and 3A. 

Let's Look at each subtree separately in the figure given below. 

Subtree 3A will have three nodes, 1 node at level 0 and 2 nodes at level 1. So the sum of all depths of subtree 3A will be 1 + 1 = 2. 

Subtree 2A will have 5 nodes, 1 node at level 0, 2 nodes at level 1, 2 nodes at level 2. So sum of all depths of subtree 2A will be 1 + 1 + 2 + 2 = 6.

Subtree 2B will have 3 nodes, 1 node at level 0, 2 nodes at level 1, so the sum of all depts of subtree 2B will be 1 + 1 = 2.

Subtree 1A will have 9 nodes, and 1 node at level 0, 2 nodes at level 1, 4 nodes at level 2, 2 nodes at level 3. So sum of all depts of subtree 1A will be 1 + 1 + 2 + 2 + 2 + 2 + 3 + 3 = 16. 

So total Sum of subtree depths of given binary tree = 2 + 6 + 2 + 16 = 26. 

Now question statement should be clear. 

Let's Look at the naive approach to solve the question: 

Naive Approach

The idea is simple, traverse every node of the tree, recursively calculate the sum of depths of all nodes for that particular node, and finally print the total sum. 

Steps of Algorithm

  1. Make a function sumOfSubtree() that will calculate the sum of depths of the given root. 
  2. Make another function sumofAllSubtrees() that will call sumOfSubtree for every node, and finally calculate the total sum of all the subtrees. 

Implementation in C++

// calulating the sum of subtree depths 
#include<bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
        TreeNode *left, *right;
        int data;
        TreeNode(int data){
            this->left = NULL;
            this->right = NULL;
            this->data = data;
        }
};

int sumOfsubtree(TreeNode *root, int d){
    // if there is no node just return 0
    if(root == NULL) return 0;
    // calulating the sum of the depth of the tree
    return d + sumOfsubtree(root->left, d+1) + sumOfsubtree(root->right, d+1);
}

// recursive function to calculate the sum of subtree depths 
int sumofAllSubtrees(TreeNode *root){
    // if there is no node just return 0
    if(root==NULL) return 0;

    // calling sum function for current subtree
    // calling to left and right tree
    return sumOfsubtree(root, 0) + sumofAllSubtrees(root->left) + sumofAllSubtrees(root->right);
}

int main(){
    // creating the tree, given in the sample example
    TreeNode *root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->left->left = new TreeNode(40);
    root->left->right = new TreeNode(50);
    root->right->left = new TreeNode(60);
    root->right->right = new TreeNode(70);
    root->left->left->left = new TreeNode(80);
    root->left->left->right = new TreeNode(90);
    cout << sumofAllSubtrees(root) << endl;
}

 

Output: 

26  

 

Complexity Analysis

Time Complexity: O(N^2)

Explanation: O(N) for traversing the tree and O(N) for calculating the sum of depths for each node. So total time Complexity is O(N*N). 

Space Complexity: O(N)

Explanation: Recursive stack space will be at most O(N). 

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

Efficient Approach

The naive approach can be optimized in the following way. 

Let's P and Q are the number of nodes in the left and right subtree respectively and sum1 and sum2 are the sums of depths of nodes in the left and right subtrees. 

Therefore the sum of depths at the current node will be equal to sum1 + sum2 + P + Q, where the depths of nodes P + Q increase by 1. 

Steps of Algorithm

  1. Make the DFS Algorithm function say sumOfDepthofAllSubtree().
  2. We will use a pair 'p' that will store a total number of nodes and the total sum of depths of subtrees. 
  3. Recursively call for a left child of root if it exists and increment p.first by a total number of nodes in the left subtree and p.second by the total sum of depths of the left subtree.
  4. Similarly, recursively call for a right child of root if it exists and increment p.first by a total number of nodes in the right subtree and p.second by the total sum of depths of the right subtree.
  5. Finally, increment the ans by the total sum of depths of nodes, i.e p.second, and return the pair p. 
  6. Finally, print the 'ans' variable. 

Implementation in C++

// Program to calulating the sum of subtree depths 
#include<bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
        TreeNode *left, *right;
        int data;
        TreeNode(int data){
            this->left = NULL;
            this->right = NULL;
            this->data = data;
        }
};
int ans = 0;
// recursive function to calculate the sum of subtree depths 
pair<int,int> sumOfDepthofAllSubtree(TreeNode *root){
    // intialize the pair with depth as 0
    // and number of nodes as 1
    pair<int,int>p{1,0};

    // if right subtree exits
    if(root->right){
        // recursively call for the right subtree
        // and store the result in the temp pair
        pair<int,int>temp = sumOfDepthofAllSubtree(root->right);

        // increment the number of node
        // in the pair p of the right subtree
        p.first += temp.first;

        // increase the sum of depths subtree
        // in the pair p of the right subtree
        // i.e add total number of nodes and total sum
        p.second += temp.first + temp.second;
    }

    // if left subtree exists
    if(root->left){
        pair<int,int>temp = sumOfDepthofAllSubtree(root->left);
       
        // increment the number of node
        // in the pair p of the left subtree
        p.first += temp.first;

        // increase the sum of depths subtree
        // in the pair p of the left subtree
        // i.e add total number of nodes and total sum
        p.second += temp.first + temp.second;
    }

    // add the sum of depths of current subtree
    ans += p.second;

    // return the pair p
    return p;

}

int main(){
    // creating the tree, given in the sample example
    TreeNode *root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->left->left = new TreeNode(40);
    root->left->right = new TreeNode(50);
    root->right->left = new TreeNode(60);
    root->right->right = new TreeNode(70);
    root->left->left->left = new TreeNode(80);
    root->left->left->right = new TreeNode(90);
    sumOfDepthofAllSubtree(root);
    cout << ans << endl;
}

 

Output:

 26  

 

Complexity Analysis

Time Complexity: O(N)

Explanation: O(N) for traversing the tree only, we are just traversing the tree once. 

Space ComplexityO(N)

Explanation: Recursive stack space, will be at most O(N). 

Must Read Recursive Binary Search.

Frequently asked questions

What is the difference between a binary tree and a binary search tree?

 A tree that has a maximum of 2 children is called a binary tree, whereas a binary search tree is a particular binary tree having the following properties. Keys in the left subtree are always smaller than the root’s node, whereas keys in the right subtree are greater than the root’s node. 

What is inorder traversal ? 

In inorder traversal, we first traverse the left subtree, then visit the root and then traverse the right subtree. 

What is the difference between a full binary tree and a complete binary tree? 

A full binary tree is a binary tree in which every node has either 0 or 2 children; no one can have one child, while a complete binary tree is a tree in which all levels are filled, except possibly the last level, which will start to fill from left to right. 

What is auxiliary space

Ans: An algorithm's additional or temporary space is referred to as Auxiliary space. The overall space consumed by an algorithm in relation to the input size is known as its space complexity. Auxiliary space and input space are both included in the space complexity.

Conclusion

This article discussed the problem of finding the sum of subtree depths for every node of a given tree. We hope you understand the problem and solution properly. Now you can try the more similar questions.

Check out this problem - Pair Sum In Array.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Previous article
Sum of heights of all individual nodes in a binary tree
Next article
Sum of Distance of All Nodes From a Given Node
Live masterclass