Techiio-author
Started by David HarrisonOct 2, 2021

Open
Checking 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

Techiio-commentatorJhone 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;

}

I think I give u a satisfactory answer to your question.

You must be Logged in to reply
Techiio-logo

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.

Follow us on:

Subscribe to get latest updates

You can unsubscribe anytime from getting updates from us
Developed and maintained by Wikiance
Developed and maintained by Wikiance