Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Naive Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexities
3.
Efficient Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexities
4.
Frequently Asked Questions
4.1.
What is a perfect binary tree?
4.2.
How can you calculate the total number of nodes in a binary tree?
4.3.
What is the number of nodes in a perfect binary tree?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Sum of all nodes of the given perfect binary tree

Author Palak Mishra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss how to implement a program to print the total sum of all nodes in that given perfect binary tree. Before moving further, let's see what a Perfect Binary Tree is.

"A binary tree is considered perfect if every internal node has exactly two child nodes and every leaf node is at the same level. All internal nodes share the degree of 2."

Now, let's understand what we have to implement in the problem statement:

Problem Statement

Ninja has a binary tree. The total nodes in the tree are n. He gave the tree to you. He said he wanted to check the sum of all nodes of the respective binary tree. But, the problem is that he cannot check it alone as he is busy with other work. Can you help him with the situation and Calculate the sum of all leaves nodes in that binary tree.

Before deep-diving into the solution to this problem, we should look at some examples to help us understand the situation better.

Sample Examples

Example1:

L = levels of the respective Perfect Binary Tree

Input : 

L = 2

Output: 

18

 

Explanation: 

The sum of two nodes of a level of binary tree is 9 and since we have two levels i.e.  9*2 =18


Example 2 :

L = levels of the respective Perfect Binary Tree

Input :

L = 3

Output: 

42

 

Explanation: 

The sum of two nodes of a level of binary tree is14 and since we have three levels i.e. 14*3 = 42

Naive Approach

The problem can be quickly solved by generating values for each node in the perfect binary tree and then adding up all of those values. After we have generated all the leaf nodes, the remaining nodes can then be generated bottom-up.
We know that the number of leaf nodes in a perfect binary tree can be calculated as  2^(L-1), where L is the total number of levels.
As we move upward from the bottom of a perfect binary tree, the number of nodes will gradually decrease by half.

Algorithm

  •  Create a function that calculates the total number of nodes in a given perfect binary tree.
  • To count no. of leaf nodes, Create a vector list for storing nodes of all levels
  •  Save the leaf nodes from the previous level of nodes.
  •  By moving from the bottom up, store nodes from the remaining levels.
  •  Loop to calculate parent node values from lower-level children nodes
  •  Save the parent node's value as the sum of its children nodes.
  •  Calculate the sum by iterating through the list of vectors.

Implementation

#include <bits/stdc++.h>
using namespace std;
//function to find a sum of all nodes of a given perfect BT

 int sumofBTNodes(int l)
{

    int leafNodesBTCount = pow(2, l - 1);
    vector<int> vec[l];

    for (int i = 1; i <= leafNodesBTCount; i++)
       vec[l - 1].push_back(i);
       

    for (int i = l - 2; i >= 0; i--) 
     {
         int k = 0;
         while (k < vec[i + 1].size() - 1) 
          {
            vec[i].push_back(vec[i + 1][k] + vec[i + 1][k + 1]);
            k += 2;
          }
      }
      
    int sum = 0;
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < vec[i].size(); j++)
        sum += vec[i][j];
     }
  return sum;
}

//Main Code
int main()
{
   int l = 3;
   cout << sumofBTNodes(l);
   return 0;
}

 Output: 

30

Complexities

Time complexities: O(n2),  Sice we are using a nested loop in our approach.

Space Complexities: O(n), i.e. the amount of memory needed to run the algorithm using vector grows no faster than linearly 

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

We must determine the sum of all nodes if we look more closely. Since the leaf nodes contain values ranging from 1 to n, we can calculate their sum using the formula n(n+1)/2.

Since this is a perfect binary tree, the sum of each level will be the same. Decide on the level's sum, then multiply it by the total number of levels.

Algorithm

  • Create a function to find the sum of all of the nodes of a given perfect binary tree.
  • Count the number of leaf nodes.
  • Find the sum of nodes at the last level.
  • Now calculate the sum of all nodes.

Implementation

#include <bits/stdc++.h>
using namespace std;


// function to find a sum of all nodes of a given perfect BT


int sumNodesofBT(int l)
{

   int leafNodetotalCount = pow(2, l - 1);
   int sumofBTLastLevel = 0;

   sumofBTLastLevel = (leafNodetotalCount * (leafNodetotalCount + 1)) / 2;
   int sum = sumofBTLastLevel * l;
   return sum;
}


// Driver Code
int main()
{
   int l = 3;
   cout << sumNodesofBT(l);
   return 0;
}

Output: 

30

Complexities

Time complexity:  O(1), means that it takes a constant time, no matter the amount of data in the set.

Space Complexity: O(1) i.e.  takes the same amount of space regardless of the input size.

Check out this problem - Diameter Of Binary Tree

Frequently Asked Questions

What is a perfect binary tree?

A binary tree is considered perfect if every internal node has exactly two child nodes and every leaf node is at the same level. All internal nodes share the degree of 2.

How can you calculate the total number of nodes in a binary tree?

If the tree is not empty, move through the left subtree, add up the nodes, and store the result in the sumLeft variable. Next, navigate the right subtree, add up all the nodes, and keep the result in sumRight. Calculate the total sum by adding the temp data, sumLeft, and sumRight.

What is the number of nodes in a perfect binary tree?

The number of nodes in each case is n, and the tree's height is h. The nodes in a perfect binary tree of height h are 2h + 1 - 1.

Conclusion

As discussed in this article, the problem "Sum of all nodes of the given perfect binary tree" asks you to return the sum of all the nodes that are part of the multiple levels of the given Perfect Binary Tree. We use two different approaches to get the desired result.

We hope this article has helped you enhance your knowledge of the subject of the Perfect Binary Tree.

After reading about the traversal of the Binary tree, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about  Maximum Width In Binary Tree and Special Binary Tree. Also, see Binary Tree Zigzag Traversal and Number of balanced binary trees.

You can also practice some relevant problems at the code studio, such as:

  1. Preorder Binary Tree
  2. Construct Binary Tree From Inorder and Preorder Traversal
  3. Top View Of Binary Tree
  4. Height of the Binary Tree From Inorder and Level Order Traversal


Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

 

Previous article
Sum of All the Parent Nodes Having Child Node X
Next article
Find Sum of All Left Leaves in a Given Binary Tree
Live masterclass