Maximum sum from a tree with adjacent levels not allowed

0 0 6 minutes read

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 allowed
from collections import deque as queue
 
# A BST node
class 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
# grandchildren
def 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 code
if __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
// representation
class 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
// grandchildren
function 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 code
let 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:

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 zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek 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.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!