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.
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<bits/stdc++.h> 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)); Ā Ā Ā Ā } } |
Python3
# Python3 code for max sum with adjacent# levels not allowedfrom collections import deque as queueĀ
# A BST nodeclass Node:Ā Ā Ā Ā Ā Ā def __init__(self, x):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā self.data = xĀ Ā Ā Ā Ā Ā Ā Ā self.left = NoneĀ Ā Ā Ā Ā Ā Ā Ā self.right = NoneĀ
# Recursive function to find the maximum# sum returned for a root node and its# grandchildrendef getSumAlternate(root):Ā Ā Ā Ā Ā Ā Ā Ā Ā if (root == None):Ā Ā Ā Ā Ā Ā Ā Ā return 0Ā
Ā Ā Ā Ā sum = root.dataĀ Ā Ā Ā Ā Ā Ā Ā Ā if (root.left != None):Ā Ā Ā Ā Ā Ā Ā Ā sum += getSum(root.left.left)Ā Ā Ā Ā Ā Ā Ā Ā sum += getSum(root.left.right)Ā
Ā Ā Ā Ā if (root.right != None):Ā Ā Ā Ā Ā Ā Ā Ā 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()def getSum(root):Ā Ā Ā Ā Ā Ā Ā Ā Ā if (root == None):Ā Ā Ā Ā Ā Ā Ā Ā 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 codeif __name__ == '__main__':Ā Ā Ā Ā Ā Ā Ā Ā Ā root = Node(1)Ā Ā Ā Ā root.left = Node(2)Ā Ā Ā Ā root.right = Node(3)Ā Ā Ā Ā root.right.left = Node(4)Ā Ā Ā Ā root.right.left.right = Node(5)Ā Ā Ā Ā root.right.left.right.left = Node(6)Ā Ā Ā Ā Ā Ā Ā Ā Ā print(getSum(root))Ā
# This code is contributed by mohit kumar 29 |
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 */ |
Javascript
<script>Ā
// Javascript code for max sum with // adjacent levels not allowedĀ
// Tree node class for Binary Tree// representationclass Node{Ā Ā Ā Ā constructor(data)Ā Ā Ā Ā {Ā Ā Ā Ā Ā Ā Ā Ā this.data = data;Ā Ā Ā Ā Ā Ā Ā Ā this.left = this.right = null;Ā Ā Ā Ā }}Ā
// Recursive function to find the maximum// sum returned for a root node and its// grandchildrenfunction getSumAlternate(root){Ā Ā Ā Ā if (root == null)Ā Ā Ā Ā Ā Ā Ā Ā return 0;Ā
Ā Ā Ā Ā let 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()function getSum(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 codelet 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);Ā
document.write(getSum(root));Ā
// This code is contributed by patel2127Ā
</script> |
Output:Ā
11
Time Complexity : O(n)
Auxiliary Space: 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.
This article is contributed by Ashish Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ā
Feeling lost in the world of random DSA topics, wasting time without progress? Itās time for a change! Join our DSA course, where weāll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
