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