### C++ program to maximum sum from a tree with adjacent levels not allowed

Description:
This Program is to find the maximum sum from a tree with adjacent levels not allowed which means we need to take value from the alternate levels.Let's understand it with an example, if we start the calculation from level 1 then the 2nd which will be coming will be the level 3 then level 5 and so on i.e. the Odd no. or else if it start with level 2 then the coming level will be the level 4 then level 6 and so on i.e. Even no. and at the end we just need to check the greatest among the the two Odd level sum and Even level sum.

`Input : Tree`
```
1
/     \
2       3
/         /    \
4       5      6
/    \     /       /
7    8   9    10
/     /  \
11  12   13 ```
`Output :52`
`Explanation: Total items we can take for Odd levels are: {2, 3, 7, 8, 9, 10} = 39Total items we can take for Odd levels are:{1, 4, 5, 6, 11, 12, 13} = 52 Therefor Odd Level < Even LevelMax sum is = 52.`
`Program :`
//C++ program to maximum sum from a tree with adjacent levels not allowed #include <bits/stdc++.h> using namespace std; // tree node struct Node { int data; Node *left, *right; }; // returns a new tree Node Node* newNode(int data) { Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp; } int getSum(Node* root) { if (!root) return 0; // create a queue for level order traversal queue<Node*> q; q.push(root); int level = 0; int evenSum = 0, oddSum = 0; // traverse until the queue is empty while (!q.empty()) { int size = q.size(); level += 1; // traverse for complete level while(size > 0) { Node* temp = q.front(); q.pop(); // check if level no. is even or odd and accordingly update the evenSum or oddSum if(level % 2 == 0) evenSum += temp->data; else oddSum += temp->data; // check for left child if (temp->left) { q.push(temp->left); } // check for right child if (temp->right) { q.push(temp->right); } size -= 1; } } if(oddSum<evenSum) return (evenSum); else return (oddSum); } // driver program int main() { // construct a tree Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->right->left = newNode(5); root->right->right = newNode(6); root->left->left = newNode(4); root->left->left->left = newNode(7); root->left->left->right = newNode(8); root->right->left->left = newNode(9); root->right->right->left = newNode(10); root->left->left->left->left = newNode(11); root->left->left->right->left = newNode(12); root->left->left->right->right = newNode(13); int result = getSum(root); cout << "Sum is :: "; cout << result << endl; return 0; }

Output :

Sum is :: 52

#### More Articles of Mandeep Sheoran:

Name Views Likes
C++ program to insert an element into binary tree 6240 19
C++ program to find an element into binary tree 772 16
C++ std::is_void 572 15
C++ program to find the closest element in binary search tree 916 19
C++ program to replace every element with the least greater element on its right 573 12
C++ program to delete an element into binary tree 785 24
C++ program to find maximum element between two nodes of binary search tree 699 20
C++ std::remove_copy_if with std::vectors 547 11
C++ program to print duplicate elements from the binary search tree 2937 15
C++ program to find depth of the deepest odd level node in binary tree 575 23
C++ program to remove duplicate elements from the binary search tree 1548 20
C++ std::rotate_copy with std::vector 530 14
C++ std::copy_n with std::vector 638 22
C++ std::copy_if with std::vector 1552 18
C++ program to print all the elements of binary search tree 7105 22
C++ std::reverse_copy with std::list 598 18
C++ program to print all the elements of binary tree 1158 18
C++ program to print all full nodes in a binary tree 572 25
C++ program to find sink odd nodes in binary tree 580 15
C++ std::is_copy_assignable 596 22
C++ program to check whether a binary tree is a full binary tree or not using recursion 609 19
C++ std::is_copy_constructible 618 27
C++ program to delete an element into binary search tree 2873 18
C++ std::reverse_copy with std::vector 487 18
C++ std::rotate with std::vector 641 15
C++ program to check for symmetric binary tree using recursion 599 25
C++ program to maximum sum from a tree with adjacent levels not allowed 552 15
C++ std::copy_n with std::list 595 21
C++ program to check if two trees are identical using recursion 545 15
C++ std::copy_n 874 21
C++ std::copy_if with std::list 998 19
C++ program to print the nodes at odd levels of a tree 562 13
C++ program to find lowest common ancestor in a binary tree 689 29
C++ program to find depth of the deepest odd level leaf node 494 13
C++ std::remove_copy_if with std::list 666 20
C++ program to add all greater values to every node in a given binary search tree 638 15