# Maximum sum from a tree with adjacent levels not allowed

Given a binary tree with positive integer values. Find the maximum sum of nodes such that we cannot pick two levels for computing sum

```Examples:

Input : Tree
1
/
2   3
/
4

5
/
6

Output :11
Explanation: Total items we can take: {1, 4, 6}
or {2, 3, 5}. Max sum = 11.

Input : Tree
1
/
2     3
/      /
4       5     6
/       /     /
17  18   19    30
/     /
11    12   13
Output :89
Explanation: Total items we can take: {2, 3, 17, 18,
19, 30} or {1, 4, 5, 6, 11, 12, 13}.
Max sum from first set = 89.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Explanation: We know that we need to get item values from alternate tree levels. This means that if we pick from level 1, the next pick would be from level 3, then level 5 and so on. Similarly, if we start from level 2, next pick will be from level 4, then level 6 and so on. So, we actually need to recursively sum all the grandchildren of a particular element as those are guaranteed to be at the alternate level.

We know for any node of tree, there are 4 grandchildren of it.

```    grandchild1 = root.left.left;
grandchild2 = root.left.right;
grandchild3 = root.right.left;
grandchild4 = root.right.right;
```

We can recursively call the getSum() method in the below program to find the sum of these children and their grandchildren. At the end, we just need to return maximum sum obtained by starting at level 1 and starting at level 2.

## C++

 `// C++ code for max sum with adjacent levels  ` `// not allowed  ` `#include  ` `using` `namespace` `std; ` ` `  `    ``// Tree node class for Binary Tree  ` `    ``// representation  ` `    ``struct` `Node  ` `    ``{  ` `        ``int` `data;  ` `        ``Node* left, *right;  ` `        ``Node(``int` `item)  ` `        ``{  ` `            ``data = item;  ` `        ``}  ` `    ``} ; ` ` `  `    ``int` `getSum(Node* root) ; ` `     `  `    ``// Recursive function to find the maximum  ` `    ``// sum returned for a root node and its  ` `    ``// grandchildren  ` `    ``int` `getSumAlternate(Node* root)  ` `    ``{  ` `        ``if` `(root == NULL)  ` `            ``return` `0;  ` ` `  `        ``int` `sum = root->data;  ` `        ``if` `(root->left != NULL)  ` `        ``{  ` `            ``sum += getSum(root->left->left);  ` `            ``sum += getSum(root->left->right);  ` `        ``}  ` ` `  `        ``if` `(root->right != NULL)  ` `        ``{  ` `            ``sum += getSum(root->right->left);  ` `            ``sum += getSum(root->right->right);  ` `        ``}  ` `        ``return` `sum;  ` `    ``}  ` ` `  `    ``// Returns maximum sum with adjacent  ` `    ``// levels not allowed-> This function  ` `    ``// mainly uses getSumAlternate()  ` `    ``int` `getSum(Node* root)  ` `    ``{  ` `        ``if` `(root == NULL)  ` `            ``return` `0;  ` `             `  `        ``// We compute sum of alternate levels  ` `        ``// starting first level and from second  ` `        ``// level->  ` `        ``// And return maximum of two values->  ` `        ``return` `max(getSumAlternate(root),  ` `                        ``(getSumAlternate(root->left) +  ` `                        ``getSumAlternate(root->right)));  ` `    ``}  ` ` `  `    ``// Driver function  ` `    ``int` `main() ` `    ``{  ` `        ``Node* root = ``new` `Node(1);  ` `        ``root->left = ``new` `Node(2);  ` `        ``root->right = ``new` `Node(3);  ` `        ``root->right->left = ``new` `Node(4);  ` `        ``root->right->left->right = ``new` `Node(5);  ` `        ``root->right->left->right->left = ``new` `Node(6);  ` `        ``cout << (getSum(root));  ` `        ``return` `0; ` `    ``} ` `     `  `// This code is contributed by Arnab Kundu `

## Java

 `// Java code for max sum with adjacent levels ` `// not allowed ` `import` `java.util.*; ` ` `  `public` `class` `Main { ` ` `  `    ``// Tree node class for Binary Tree ` `    ``// representation ` `    ``static` `class` `Node { ` `        ``int` `data; ` `        ``Node left, right; ` `        ``Node(``int` `item) ` `        ``{ ` `            ``data = item; ` `            ``left = right = ``null``; ` `        ``} ` `    ``} ` ` `  `    ``// Recursive function to find the maximum ` `    ``// sum returned for a root node and its ` `    ``// grandchildren ` `    ``public` `static` `int` `getSumAlternate(Node root) ` `    ``{ ` `        ``if` `(root == ``null``) ` `            ``return` `0``; ` ` `  `        ``int` `sum = root.data; ` `        ``if` `(root.left != ``null``) { ` `            ``sum += getSum(root.left.left); ` `            ``sum += getSum(root.left.right); ` `        ``} ` ` `  `        ``if` `(root.right != ``null``) { ` `            ``sum += getSum(root.right.left); ` `            ``sum += getSum(root.right.right); ` `        ``} ` `        ``return` `sum; ` `    ``} ` ` `  `    ``// Returns maximum sum with adjacent ` `    ``// levels not allowed. This function ` `    ``// mainly uses getSumAlternate() ` `    ``public` `static` `int` `getSum(Node root) ` `    ``{ ` `        ``if` `(root == ``null``) ` `            ``return` `0``; ` ` `  `        ``// We compute sum of alternate levels ` `        ``// starting first level and from second ` `        ``// level. ` `        ``// And return maximum of two values. ` `        ``return` `Math.max(getSumAlternate(root), ` `                        ``(getSumAlternate(root.left) + ` `                         ``getSumAlternate(root.right))); ` `    ``} ` ` `  `    ``// Driver function ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``Node root = ``new` `Node(``1``); ` `        ``root.left = ``new` `Node(``2``); ` `        ``root.right = ``new` `Node(``3``); ` `        ``root.right.left = ``new` `Node(``4``); ` `        ``root.right.left.right = ``new` `Node(``5``); ` `        ``root.right.left.right.left = ``new` `Node(``6``); ` `        ``System.out.println(getSum(root)); ` `    ``} ` `} `

## C#

 `// C# code for max sum with adjacent levels ` `// not allowed ` `using` `System; ` ` `  `class` `GFG ` `{ ` ` `  `    ``// Tree node class for Binary Tree ` `    ``// representation ` `    ``public` `class` `Node ` `    ``{ ` `        ``public` `int` `data; ` `        ``public` `Node left, right; ` `        ``public` `Node(``int` `item) ` `        ``{ ` `            ``data = item; ` `            ``left = right = ``null``; ` `        ``} ` `    ``} ` ` `  `    ``// Recursive function to find the maximum ` `    ``// sum returned for a root node and its ` `    ``// grandchildren ` `    ``public` `static` `int` `getSumAlternate(Node root) ` `    ``{ ` `        ``if` `(root == ``null``) ` `            ``return` `0; ` ` `  `        ``int` `sum = root.data; ` `        ``if` `(root.left != ``null``) ` `        ``{ ` `            ``sum += getSum(root.left.left); ` `            ``sum += getSum(root.left.right); ` `        ``} ` ` `  `        ``if` `(root.right != ``null``)  ` `        ``{ ` `            ``sum += getSum(root.right.left); ` `            ``sum += getSum(root.right.right); ` `        ``} ` `        ``return` `sum; ` `    ``} ` ` `  `    ``// Returns maximum sum with adjacent ` `    ``// levels not allowed. This function ` `    ``// mainly uses getSumAlternate() ` `    ``public` `static` `int` `getSum(Node root) ` `    ``{ ` `        ``if` `(root == ``null``) ` `            ``return` `0; ` ` `  `        ``// We compute sum of alternate levels ` `        ``// starting first level and from second ` `        ``// level. ` `        ``// And return maximum of two values. ` `        ``return` `Math.Max(getSumAlternate(root), ` `                        ``(getSumAlternate(root.left) + ` `                        ``getSumAlternate(root.right))); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``Node root = ``new` `Node(1); ` `        ``root.left = ``new` `Node(2); ` `        ``root.right = ``new` `Node(3); ` `        ``root.right.left = ``new` `Node(4); ` `        ``root.right.left.right = ``new` `Node(5); ` `        ``root.right.left.right.left = ``new` `Node(6); ` `        ``Console.WriteLine(getSum(root)); ` `    ``} ` `} ` ` `  `/* This code contributed by PrinciRaj1992 */`

Output:

```11
```

Time Complexity : O(n)

Exercise: Try printing the same solution for a n-ary Tree rather than a binary tree. The trick lies in the representation of the tree.

Tree Tree