 Started by David HarrisonOct 2, 2021

# OpenChecking if the sums of the levels of a Binary Tree are equal

1 VIEWES 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 1 VIEWES SHARE

I'm trying to figure out a function in c++ to calculate the sums of all the levels of a binary tree and then checking if those sums are all equal, and returning TRUE if they are.

So for example, if the first node is 10, the sum of its children has to be 10, and the sum of their children has to be 10, and so on...

I'm having truble comparing the sums without the recursions getting in the way. And the comparison has to be done in the function itself, not the main.

1 Replies Jhone Buttler replied a month ago0 likes0 dislikes

if you have defined the Node data as follows

`struct TreeNode {`

` int val;`

` TreeNode *left;`

` TreeNode *right;`

` TreeNode() : val(0), left(nullptr), right(nullptr) {}`

` TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}`

` TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}`

`};`

Then you can perform level order traversal without recursion as follows.

1. Initialize a queue

2. store the root node in the queue

3. now traverse children until the queue is empty

4. while traversing, if you find left or right children you have to push them again into the queue

Here's the basic code that does what you wanted

`bool equalSums(TreeNode* root) {`

` if(root == nullptr){`

` return true;`

` }`

` `

` queue<TreeNode*> q;`

` `

` //push the root`

` q.push(root);`

` int sum = root->val; //save the current root value`

` int len;`

` TreeNode *temp;`

` while(!q.empty()){`

` int s = 0; //keep track of the next levels sum`

` len = q.size(); //size of queue is number of elements at that level`

` `

` for(int i=0; i<len; i++){`

` temp = q.front();`

` q.pop();`

` `

` s = s+temp->val;`

` `

` if(temp->left)`

` q.push(temp->left);`

` if(temp->right)`

` q.push(temp->right);`

` }`

` `

` // break if sum is not equal to sum of node values in current level`

` if(s != sum)`

` return false;`

` }`

` `

` // else return true`

` return true;`

` }`

You must be Logged in to reply
Trending Technologies
15 Software40 DevOps47 Frontend Development24 Backend Development20 Server Administration17 Linux Administration26 Data Center24 Sentry24 Terraform23 Ansible83 Docker70 Penetration Testing16 Kubernetes21 NGINX20 JenkinsX17
Recommended Blogs
3   8 Bell Grant Bell Grant Bell Grant David Harrison David Harrison David Harrison David Harrison Peter Daniels Techiio is on the journey to build an ocean of technical knowledge, scouring the emerging stars in process and proffering them to the corporate world.