Open In App

Maximum sum of nodes in Binary tree such that no two are adjacent

Last Updated : 09 Mar, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given a binary tree with a value associated with each node, we need to choose a subset of these nodes such that the sum of selected nodes is maximum under a constraint that no two chosen nodes in the subset should be directly connected, that is, if we have taken a node in our sum then we can’t take any of its children in consideration and vice versa

Examples:  

Input:

Explanation: In the above binary tree, chosen nodes are encircled and are not directly connected, and their sum is the maximum possible

Recommended: Please solve it on “PRACTICE” first before moving on to the solution.

The maximum sum of nodes in a Binary tree such that no two are adjacent using Recursion:

We can solve this problem by considering the fact that both node and its children can’t be in sum at the same time, so when we take a node into our sum, we will call recursively for its grandchildren or if we don’t take this node then we will call for all its children nodes and finally we will choose maximum from both of the results. 

It can be seen easily that the above approach can lead to solving the same subproblem many times, for example in the above diagram node 1 calls node 4 and 5 when its value is chosen and node 3 also calls them when its value is not chosen so these nodes are processed more than once. We can stop solving these nodes more than once by memorizing the result at all nodes

Follow the below steps to solve the problem:

  • Create a map to memorize the results
  • Recur to solve the problem for the root node
  • If the root is NULL return 0 (Base Case)
  • If the answer to this subproblem is already stored in the map, then return it
  • Now either include the current node and recur for its grandchildren 
  • or don’t take the current node and recur for its left and the right child
  • Save the answer to this problem equal to the maximum of the above two cases
  • Return the answer

Below is the implementation of the above approach:

C++




// C++ program to find maximum sum from a subset of
// nodes of binary tree
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node structure */
struct node {
    int data;
    struct node *left, *right;
};
 
/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
    struct node* temp = new struct node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
//  Declaration of methods
int sumOfGrandChildren(node* node,
                       map<struct node*, int>& mp);
int getMaxSum(node* node);
int getMaxSumUtil(node* node, map<struct node*, int>& mp);
 
// method returns maximum sum possible from subtrees rooted
// at grandChildrens of node 'node'
int sumOfGrandChildren(node* node,
                       map<struct node*, int>& mp)
{
    int sum = 0;
 
    //  call for children of left child only if it is not
    //  NULL
    if (node->left)
        sum += getMaxSumUtil(node->left->left, mp)
               + getMaxSumUtil(node->left->right, mp);
 
    //  call for children of right child only if it is not
    //  NULL
    if (node->right)
        sum += getMaxSumUtil(node->right->left, mp)
               + getMaxSumUtil(node->right->right, mp);
 
    return sum;
}
 
//  Utility method to return maximum sum rooted at node
//  'node'
int getMaxSumUtil(node* node, map<struct node*, int>& mp)
{
    if (node == NULL)
        return 0;
 
    // If node is already processed then return calculated
    // value from map
    if (mp.find(node) != mp.end())
        return mp[node];
 
    //  take current node value and call for all grand
    //  children
    int incl = node->data + sumOfGrandChildren(node, mp);
 
    //  don't take current node value and call for all
    //  children
    int excl = getMaxSumUtil(node->left, mp)
               + getMaxSumUtil(node->right, mp);
 
    //  choose maximum from both above calls and store that
    //  in map
    mp[node] = max(incl, excl);
 
    return mp[node];
}
 
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
int getMaxSum(node* node)
{
    if (node == NULL)
        return 0;
    map<struct node*, int> mp;
    return getMaxSumUtil(node, mp);
}
 
//  Driver code
int main()
{
    node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->left->left = newNode(1);
 
    cout << getMaxSum(root) << endl;
    return 0;
}


Java




// Java program to find maximum sum from a subset of
// nodes of binary tree
import java.util.HashMap;
public class FindSumOfNotAdjacentNodes {
 
    // method returns maximum sum possible from subtrees
    // rooted at grandChildrens of node 'node'
    public static int
    sumOfGrandChildren(Node node, HashMap<Node, Integer> mp)
    {
        int sum = 0;
        //  call for children of left child only if it is
        //  not NULL
        if (node.left != null)
            sum += getMaxSumUtil(node.left.left, mp)
                   + getMaxSumUtil(node.left.right, mp);
 
        //  call for children of right child only if it is
        //  not NULL
        if (node.right != null)
            sum += getMaxSumUtil(node.right.left, mp)
                   + getMaxSumUtil(node.right.right, mp);
        return sum;
    }
 
    //  Utility method to return maximum sum rooted at node
    //  'node'
    public static int
    getMaxSumUtil(Node node, HashMap<Node, Integer> mp)
    {
        if (node == null)
            return 0;
 
        // If node is already processed then return
        // calculated value from map
        if (mp.containsKey(node))
            return mp.get(node);
 
        //  take current node value and call for all grand
        //  children
        int incl = node.data + sumOfGrandChildren(node, mp);
 
        //  don't take current node value and call for all
        //  children
        int excl = getMaxSumUtil(node.left, mp)
                   + getMaxSumUtil(node.right, mp);
 
        //  choose maximum from both above calls and store
        //  that in map
        mp.put(node, Math.max(incl, excl));
 
        return mp.get(node);
    }
 
    // Returns maximum sum from subset of nodes
    // of binary tree under given constraints
    public static int getMaxSum(Node node)
    {
        if (node == null)
            return 0;
        HashMap<Node, Integer> mp = new HashMap<>();
        return getMaxSumUtil(node, mp);
    }
 
      // Driver code
    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.right = new Node(5);
        root.left.left = new Node(1);
        System.out.print(getMaxSum(root));
    }
}
 
/* A binary tree node structure */
class Node {
    int data;
    Node left, right;
    Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
// This code is contributed by Gaurav Tiwari


Python3




# Python3 program to find
# maximum sum from a subset
# of nodes of binary tree
 
# A binary tree node structure
 
 
class Node:
 
    def __init__(self, data):
 
        self.data = data
        self.left = None
        self.right = None
 
# Utility function to create
# a new Binary Tree node
 
 
def newNode(data):
 
    temp = Node(data)
    return temp
 
# method returns maximum sum
# possible from subtrees rooted
# at grandChildrens of node 'node'
 
 
def sumOfGrandChildren(node, mp):
 
    sum = 0
 
    # call for children of left
    # child only if it is not NULL
    if (node.left):
        sum += (getMaxSumUtil(node.left.left, mp) +
                getMaxSumUtil(node.left.right, mp))
 
    # call for children of right
    # child only if it is not NULL
    if (node.right):
        sum += (getMaxSumUtil(node.right.left, mp) +
                getMaxSumUtil(node.right.right, mp))
 
    return sum
 
# Utility method to return
# maximum sum rooted at node
# 'node'
 
 
def getMaxSumUtil(node, mp):
 
    if (node == None):
        return 0
 
    # If node is already processed
    # then return calculated
    # value from map
    if node in mp:
        return mp[node]
 
    # take current node value
    # and call for all grand children
    incl = (node.data +
            sumOfGrandChildren(node, mp))
 
    # don't take current node
    # value and call for all children
    excl = (getMaxSumUtil(node.left, mp) +
            getMaxSumUtil(node.right, mp))
 
    # choose maximum from both
    # above calls and store that
    # in map
    mp[node] = max(incl, excl)
 
    return mp[node]
 
# Returns maximum sum from
# subset of nodes of binary
# tree under given constraints
 
 
def getMaxSum(node):
 
    if (node == None):
        return 0
 
    mp = dict()
    return getMaxSumUtil(node, mp)
 
 
# Driver code
if __name__ == "__main__":
 
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.right.left = newNode(4)
    root.right.right = newNode(5)
    root.left.left = newNode(1)
 
    print(getMaxSum(root))
 
# This code is contributed by Rutvik_56


C#




// C# program to find maximum sum from a subset of
// nodes of binary tree
using System;
using System.Collections.Generic;
 
public class FindSumOfNotAdjacentNodes {
 
    // method returns maximum sum
    // possible from subtrees rooted
    // at grandChildrens of node 'node'
    public static int
    sumOfGrandChildren(Node node, Dictionary<Node, int> mp)
    {
        int sum = 0;
 
        // call for children of left
        // child only if it is not NULL
        if (node.left != null)
            sum += getMaxSumUtil(node.left.left, mp)
                   + getMaxSumUtil(node.left.right, mp);
 
        // call for children of right
        // child only if it is not NULL
        if (node.right != null)
            sum += getMaxSumUtil(node.right.left, mp)
                   + getMaxSumUtil(node.right.right, mp);
        return sum;
    }
 
    // Utility method to return maximum
    // sum rooted at node 'node'
    public static int
    getMaxSumUtil(Node node, Dictionary<Node, int> mp)
    {
        if (node == null)
            return 0;
 
        // If node is already processed then
        // return calculated value from map
        if (mp.ContainsKey(node))
            return mp[node];
 
        // take current node value and
        // call for all grand children
        int incl = node.data + sumOfGrandChildren(node, mp);
 
        // don't take current node value and
        // call for all children
        int excl = getMaxSumUtil(node.left, mp)
                   + getMaxSumUtil(node.right, mp);
 
        // choose maximum from both above
        // calls and store that in map
        mp.Add(node, Math.Max(incl, excl));
 
        return mp[node];
    }
 
    // Returns maximum sum from subset of nodes
    // of binary tree under given constraints
    public static int getMaxSum(Node node)
    {
        if (node == null)
            return 0;
        Dictionary<Node, int> mp
            = new Dictionary<Node, int>();
        return getMaxSumUtil(node, mp);
    }
 
    // Driver code
    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.right = new Node(5);
        root.left.left = new Node(1);
        Console.Write(getMaxSum(root));
    }
}
 
/* A binary tree node structure */
public class Node {
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
// This code has been contributed by 29AjayKumar


Javascript




<script>
 
// Javascript program to find maximum
// sum from a subset of nodes of binary tree
class Node
{
    constructor(data)
    {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}
 
// Method returns maximum sum possible
// from subtrees rooted at grandChildrens
// of node 'node'
function sumOfGrandChildren(node, mp)
{
    let sum = 0;
     
    // Call for children of left child
    // only if it is not NULL
    if (node.left!=null)
        sum += getMaxSumUtil(node.left.left, mp) +
               getMaxSumUtil(node.left.right, mp);
 
    // Call for children of right child
    // only if it is not NULL
    if (node.right!=null)
        sum += getMaxSumUtil(node.right.left, mp) +
               getMaxSumUtil(node.right.right, mp);
    return sum;
}
 
// Utility method to return maximum
// sum rooted at node 'node'
function getMaxSumUtil(node, mp)
{
    if (node == null)
        return 0;
 
    // If node is already processed then return
    // calculated value from map
    if (mp.has(node))
        return mp.get(node);
 
    // Take current node value and call for
    // all grand children
    let incl = node.data + sumOfGrandChildren(node, mp);
 
    // Don't take current node value and call
    // for all children
    let excl = getMaxSumUtil(node.left, mp) +
               getMaxSumUtil(node.right, mp);
 
    // Choose maximum from both above
    // calls and store that in map
    mp.set(node,Math.max(incl, excl));
 
    return mp.get(node);
}
 
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
function getMaxSum(node)
{
    if (node == null)
        return 0;
         
    let mp = new Map();
    return getMaxSumUtil(node, mp);
}
 
// 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.right = new Node(5);
root.left.left = new Node(1);   
 
document.write(getMaxSum(root));
 
// This code is contributed by divyeshrabadiya07
 
</script>


Output

11

Time complexity: O(N)
Auxiliary Space: O(N)

The maximum sum of nodes in a Binary tree such that no two are adjacent using pair:

Return a pair for each node in the binary tree such that the first of the pair indicates the maximum sum when the data of a node is included and the second indicates the maximum sum when the data of a particular node is not included

Follow the below steps to solve the problem:

  • Recur to solve the problem for the root node
  • If the root is NULL return 0 (Base Case)
  • Create a pair of <int, int> sum1 and set sum1 equal to the answer of root->left child
  • Create a pair of <int, int> sum2 and set sum2 equal to the answer of root->right child
  • Create a pair of <int, int> sum and set sum.first equal to sum1.second + sum2.second + root->data
  • Set sum.second equal to the maximum of (sum1.first, sum1.second) + maximum of (sum2.first, sum2.second)
  • Return sum

Below is the implementation of the above approach:

C++




// C++ program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
pair<int, int> maxSumHelper(Node* root)
{
    if (root == NULL) {
        pair<int, int> sum(0, 0);
        return sum;
    }
    pair<int, int> sum1 = maxSumHelper(root->left);
    pair<int, int> sum2 = maxSumHelper(root->right);
    pair<int, int> sum;
 
    // This node is included (Left and right children
    // are not included)
    sum.first = sum1.second + sum2.second + root->data;
 
    // This node is excluded (Either left or right
    // child is included)
    sum.second = max(sum1.first, sum1.second)
                 + max(sum2.first, sum2.second);
 
    return sum;
}
 
int maxSum(Node* root)
{
    pair<int, int> res = maxSumHelper(root);
    return max(res.first, res.second);
}
 
// Driver code
int main()
{
    Node* root = new Node(10);
    root->left = new Node(1);
    root->left->left = new Node(2);
    root->left->left->left = new Node(1);
    root->left->right = new Node(3);
    root->left->right->left = new Node(4);
    root->left->right->right = new Node(5);
    cout << maxSum(root);
    return 0;
}


Java




// Java program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
public class FindSumOfNotAdjacentNodes {
 
    public static Pair maxSumHelper(Node root)
    {
        if (root == null) {
            Pair sum = new Pair(0, 0);
            return sum;
        }
        Pair sum1 = maxSumHelper(root.left);
        Pair sum2 = maxSumHelper(root.right);
        Pair sum = new Pair(0, 0);
 
        // This node is included (Left and right children
        // are not included)
        sum.first = sum1.second + sum2.second + root.data;
 
        // This node is excluded (Either left or right
        // child is included)
        sum.second = Math.max(sum1.first, sum1.second)
                     + Math.max(sum2.first, sum2.second);
 
        return sum;
    }
 
    // Returns maximum sum from subset of nodes
    // of binary tree under given constraints
    public static int maxSum(Node root)
    {
        Pair res = maxSumHelper(root);
        return Math.max(res.first, res.second);
    }
 
    // Driver code
    public static void main(String args[])
    {
        Node root = new Node(10);
        root.left = new Node(1);
        root.left.left = new Node(2);
        root.left.left.left = new Node(1);
        root.left.right = new Node(3);
        root.left.right.left = new Node(4);
        root.left.right.right = new Node(5);
        System.out.print(maxSum(root));
    }
}
 
/* A binary tree node structure */
class Node {
    int data;
    Node left, right;
    Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
/* Pair class */
class Pair {
    int first, second;
    Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
// This code is contributed by Gaurav Tiwari


Python3




# Python3 program to find maximum sum in Binary
# Tree such that no two nodes are adjacent.
 
# Binary Tree Node
 
""" utility that allocates a newNode
with the given key """
 
 
class newNode:
 
    # Construct to create a newNode
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
 
 
def maxSumHelper(root):
 
    if (root == None):
 
        sum = [0, 0]
        return sum
 
    sum1 = maxSumHelper(root.left)
    sum2 = maxSumHelper(root.right)
    sum = [0, 0]
 
    # This node is included (Left and right
    # children are not included)
    sum[0] = sum1[1] + sum2[1] + root.data
 
    # This node is excluded (Either left or
    # right child is included)
    sum[1] = (max(sum1[0], sum1[1]) +
              max(sum2[0], sum2[1]))
 
    return sum
 
 
def maxSum(root):
 
    res = maxSumHelper(root)
    return max(res[0], res[1])
 
 
# Driver Code
if __name__ == '__main__':
    root = newNode(10)
    root.left = newNode(1)
    root.left.left = newNode(2)
    root.left.left.left = newNode(1)
    root.left.right = newNode(3)
    root.left.right.left = newNode(4)
    root.left.right.right = newNode(5)
    print(maxSum(root))
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)


C#




// C# program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
using System;
 
public class FindSumOfNotAdjacentNodes {
 
    public static Pair maxSumHelper(Node root)
    {
        Pair sum;
        if (root == null) {
            sum = new Pair(0, 0);
            return sum;
        }
        Pair sum1 = maxSumHelper(root.left);
        Pair sum2 = maxSumHelper(root.right);
        Pair sum3 = new Pair(0, 0);
 
        // This node is included (Left and
        // right children are not included)
        sum3.first = sum1.second + sum2.second + root.data;
 
        // This node is excluded (Either left
        // or right child is included)
        sum3.second = Math.Max(sum1.first, sum1.second)
                      + Math.Max(sum2.first, sum2.second);
 
        return sum3;
    }
 
    // Returns maximum sum from subset of nodes
    // of binary tree under given constraints
    public static int maxSum(Node root)
    {
        Pair res = maxSumHelper(root);
        return Math.Max(res.first, res.second);
    }
 
    // Driver code
    public static void Main()
    {
        Node root = new Node(10);
        root.left = new Node(1);
        root.left.left = new Node(2);
        root.left.left.left = new Node(1);
        root.left.right = new Node(3);
        root.left.right.left = new Node(4);
        root.left.right.right = new Node(5);
        Console.Write(maxSum(root));
    }
}
 
/* A binary tree node structure */
public class Node {
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
/* Pair class */
public class Pair {
    public int first, second;
    public Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
/* This code is contributed PrinciRaj1992 */


Javascript




<script>
 
// JavaScript program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
 
/* A binary tree node structure */
class Node
{
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
/* Pair class */
class Pair
{
    constructor(first, second)
    {
        this.first = first;
        this.second = second;
    }
}
 
function maxSumHelper(root)
{
    var sum;
    if (root == null)
    {
        sum=new Pair(0, 0);
        return sum;
    }
    var sum1 = maxSumHelper(root.left);
    var sum2 = maxSumHelper(root.right);
    var sum3 = new Pair(0,0);
 
    // This node is included (Left and
    // right children are not included)
    sum3.first = sum1.second + sum2.second + root.data;
 
    // This node is excluded (Either left
    // or right child is included)
    sum3.second = Math.max(sum1.first, sum1.second) +
                Math.max(sum2.first, sum2.second);
 
    return sum3;
}
// Returns maximum sum from subset of nodes
// of binary tree under given constraints
function maxSum(root)
{
    var res=maxSumHelper(root);
    return Math.max(res.first, res.second);
}
// Driver code
var root = new Node(10);
root.left = new Node(1);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
root.left.right = new Node(3);
root.left.right.left = new Node(4);
root.left.right.right = new Node(5);
document.write(maxSum(root));
 
 
</script>


Output

21

Time complexity: O(N)
Auxiliary Space: O(N)

Thanks to Surbhi Rastogi for suggesting this method.

The maximum sum of nodes in a Binary tree such that no two are adjacent using Dynamic programming:

Store the maximum sum by including a node or excluding the node in a dp array or unordered map. Recursively call for grandchildren of nodes if the node is included or calls for its neighbors if the node is excluded

Below is the implementation of the above approach:

C++




// C++ program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
// declare map /dp array as global
unordered_map<Node*, int> umap;
int maxSum(Node* root)
{
    // base case
    if (!root)
        return 0;
 
    // if the max sum from the  node is already in
    // map,return the value
    if (umap[root])
        return umap[root];
 
    // if the current node(root) is included in result
    // then find maximum sum
    int inc = root->data;
 
    // if left of node exists, add their grandchildren
    if (root->left) {
        inc += maxSum(root->left->left)
               + maxSum(root->left->right);
    }
    // if right of node exist,add their grandchildren
    if (root->right) {
        inc += maxSum(root->right->left)
               + maxSum(root->right->right);
    }
 
    // if the current node(root) is excluded, find the
    // maximum sum
    int ex = maxSum(root->left) + maxSum(root->right);
 
    // store the maximum of including & excluding the node
    // in map
    umap[root] = max(inc, ex);
    return max(inc, ex);
}
 
// Driver code
int main()
{
    Node* root = new Node(10);
    root->left = new Node(1);
    root->left->left = new Node(2);
    root->left->left->left = new Node(1);
    root->left->right = new Node(3);
    root->left->right->left = new Node(4);
    root->left->right->right = new Node(5);
    cout << maxSum(root);
    return 0;
}


Java




/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
// Java program for the above approach
class GFG {
 
    // Java program to find maximum sum in Binary Tree
    // such that no two nodes are adjacent.
 
    // declare map /dp array as global
    static HashMap<Node, Integer> umap = new HashMap<>();
    static int maxSum(Node root)
    {
        // base case
        if (root == null)
            return 0;
 
        // if the max sum from the node is already in
        // map,return the value
        if (umap.containsKey(root))
            return umap.get(root);
 
        // if the current node(root) is included in result
        // then find maximum sum
        int inc = root.data;
 
        // if left of node exists, add their grandchildren
        if (root.left != null) {
            inc += maxSum(root.left.left)
                   + maxSum(root.left.right);
        }
        // if right of node exist,add their grandchildren
        if (root.right != null) {
            inc += maxSum(root.right.left)
                   + maxSum(root.right.right);
        }
 
        // if the current node(root) is excluded, find the
        // maximum sum
        int ex = maxSum(root.left) + maxSum(root.right);
 
        // store the maximum of including & excluding the
        // node in map
        umap.put(root, Math.max(inc, ex));
        return Math.max(inc, ex);
    }
 
    public static void main(String args[])
    {
        Node root = new Node(10);
        root.left = new Node(1);
        root.left.left = new Node(2);
        root.left.left.left = new Node(1);
        root.left.right = new Node(3);
        root.left.right.left = new Node(4);
        root.left.right.right = new Node(5);
        System.out.println(maxSum(root));
    }
}
 
// Driver code
class Node {
 
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
 
// This code is contributed by code_hunt.


Python3




# Python program to find maximum sum in Binary Tree
# such that no two nodes are adjacent.
 
 
class Node:
    def __init__(self, data):
 
        self.data = data
        self.left = None
        self.right = None
 
 
# declare map /dp array as global
umap = {}
 
 
def maxSum(root):
 
    global umap
 
    # base case
    if (root == None):
        return 0
 
    # if the max sum from the node is already in
    # map,return the value
    if (root in umap):
        return umap[root]
 
    # if the current node(root) is included in result
    # then find maximum sum
    inc = root.data
 
    # if left of node exists, add their grandchildren
    if (root.left):
        inc += maxSum(root.left.left) + maxSum(root.left.right)
 
    # if right of node exist,add their grandchildren
    if (root.right):
        inc += maxSum(root.right.left) + maxSum(root.right.right)
 
    # if the current node(root) is excluded, find the
    # maximum sum
    ex = maxSum(root.left) + maxSum(root.right)
 
    # store the maximum of including & excluding the node
    # in map
    umap[root] = max(inc, ex)
    return max(inc, ex)
 
 
# Driver code
if __name__ == '__main__':
  root = Node(10)
  root.left = Node(1)
  root.left.left = Node(2)
  root.left.left.left = Node(1)
  root.left.right = Node(3)
  root.left.right.left = Node(4)
  root.left.right.right = Node(5)
  print(maxSum(root))
 
# This code is contributed by shinjanpatra


C#




// C# program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
using System;
using System.Collections.Generic;
 
/* A binary tree node structure */
public class Node {
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
class GFG {
 
    // declare map /dp array as global
    static Dictionary<Node, int> umap
        = new Dictionary<Node, int>();
    static int maxSum(Node root)
    {
        // base case
        if (root == null)
            return 0;
 
        // if the max sum from the node is already in
        // map,return the value
        if (umap.ContainsKey(root))
            return umap[root];
 
        // if the current node(root) is included in result
        // then find maximum sum
        int inc = root.data;
 
        // if left of node exists, add their grandchildren
        if (root.left != null) {
            inc += maxSum(root.left.left)
                   + maxSum(root.left.right);
        }
        // if right of node exist,add their grandchildren
        if (root.right != null) {
            inc += maxSum(root.right.left)
                   + maxSum(root.right.right);
        }
 
        // if the current node(root) is excluded, find the
        // maximum sum
        int ex = maxSum(root.left) + maxSum(root.right);
 
        // store the maximum of including & excluding the
        // node in map
        umap.Add(root, Math.Max(inc, ex));
        return Math.Max(inc, ex);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        Node root = new Node(10);
        root.left = new Node(1);
        root.left.left = new Node(2);
        root.left.left.left = new Node(1);
        root.left.right = new Node(3);
        root.left.right.left = new Node(4);
        root.left.right.right = new Node(5);
        Console.Write(maxSum(root));
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)


Javascript




<script>
 
// JavaScript program to find maximum sum in Binary Tree
// such that no two nodes are adjacent.
class Node {
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
 
// declare map /dp array as global
let umap = new Map();
function maxSum(root)
{
    // base case
    if (!root)
        return 0;
 
    // if the max sum from the node is already in
    // map,return the value
    if (umap.has(root))
        return umap.get(root);
 
    // if the current node(root) is included in result
    // then find maximum sum
    let inc = root.data;
 
    // if left of node exists, add their grandchildren
    if (root.left) {
        inc += maxSum(root.left.left)
            + maxSum(root.left.right);
    }
    // if right of node exist,add their grandchildren
    if (root.right) {
        inc += maxSum(root.right.left)
            + maxSum(root.right.right);
    }
 
    // if the current node(root) is excluded, find the
    // maximum sum
    let ex = maxSum(root.left) + maxSum(root.right);
 
    // store the maximum of including & excluding the node
    // in map
    umap.set(root,Math.max(inc, ex));
    return Math.max(inc, ex);
}
 
// Driver code
let root = new Node(10);
root.left = new Node(1);
root.left.left = new Node(2);
root.left.left.left = new Node(1);
root.left.right = new Node(3);
root.left.right.left = new Node(4);
root.left.right.right = new Node(5);
document.write(maxSum(root));
 
// This code is contributed by shinjanpatra
</script>


Output

21

Time complexity: O(N)
Auxiliary Space: O(N)

<https://auth.geeksforgeeks.org/user/harshchandekar10/profile>

Approach: To solve the problem follow the below idea:

For every node, we find the following:

  • The maximum sum of non-adjacent nodes including the node.
  • The maximum sum of non-adjacent nodes excluding the node.

Now, we return both values in the recursive call. The parent node of the previously calculated node gets the maximum sum (including & excluding) of the child node. Accordingly, the parent now calculates the maximum sum(including & excluding) and returns. This process continues till the root node. Finally, we return the max(sum including root, sum excluding root)

Below is the implementation of the above approach:

C++




// C++ Code for above approach
#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};
 
pair<int, int> max_sum(Node* root)
{
    if (!root)
        return { 0, 0 };
 
    auto left = max_sum(root->left);
    auto right = max_sum(root->right);
 
    int no_root_l = left.first, root_l = left.second;
 
    int no_root_r = right.first, root_r = right.second;
 
    int root_sum_max
        = max(max(root->data, root->data + no_root_l),
              max(root->data + no_root_r,
                  root->data + no_root_r + no_root_l));
    int no_root_sum_max = max(
        max(root_l, root_r),
        max(max(root_l + root_r, no_root_l + no_root_r),
            max(root_l + no_root_r, root_r + no_root_l)));
 
    return { no_root_sum_max, root_sum_max };
}
 
int getMaxSum(Node* root)
{
    pair<int, int> ans = max_sum(root);
    return max(ans.first, ans.second);
}
 
int main()
{
    Node* root = new Node(10);
    root->left = new Node(1);
    root->left->left = new Node(2);
    root->left->left->left = new Node(1);
    root->left->right = new Node(3);
    root->left->right->left = new Node(4);
    root->left->right->right = new Node(5);
       cout<<getMaxSum(root)<<endl;
       
    return 0;
}
 
// This code is contributed by Tapesh(tapeshdua420)


Java




// Java Code for above approach
class Node {
 
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
 
class GFG {
 
    public static List<Integer> max_sum(Node root)
    {
        if (root == null) {
            List<Integer> temp = new ArrayList<>();
            temp.add(0);
            temp.add(0);
            return temp;
        }
        List<Integer> left = max_sum(root.left);
        List<Integer> right = max_sum(root.right);
 
        int no_root_l = left.get(0), root_l = left.get(1);
        int no_root_r = right.get(0), root_r = right.get(1);
 
        int root_sum_max = Math.max(
            Math.max(root.data, root.data + no_root_l),
            Math.max(root.data + no_root_r,
                     root.data + no_root_r + no_root_l));
        int no_root_sum_max = Math.max(
            Math.max(root_l, root_r),
            Math.max(Math.max(root_l + root_r,
                              no_root_l + no_root_r),
                     Math.max(root_l + no_root_r,
                              root_r + no_root_l)));
 
        List<Integer> ans = new ArrayList<>();
        ans.add(no_root_sum_max);
        ans.add(root_sum_max);
 
        return ans;
    }
 
    public static int getMaxSum(Node root)
    {
        List<Integer> ans = max_sum(root);
        return Math.max(ans.get(0), ans.get(1));
    }
}
 
// This code is contributed by Tapesh(tapeshdua420)


Python3




class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None
 
 
class Solution:
 
    def max_sum(self, root):
        if not root:
            return 0, 0
 
        no_root_l, root_l = self.max_sum(root.left)
        no_root_r, root_r = self.max_sum(root.right)
 
        root_sum_max = max(root.data, root.data+no_root_l,
                           root.data+no_root_r, root.data+no_root_r+no_root_l)
        no_root_sum_max = max(root_l, root_r, root_l + root_r, no_root_l+no_root_r,
                              root_l + no_root_r, root_r + no_root_l)
 
        return no_root_sum_max, root_sum_max
 
    def getMaxSum(self, root):
        return max(self.max_sum(root))


C#




// C# Code for above approach
class Node {
 
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
 
class GFG {
    public static List<int> max_sum(Node root)
    {
        if (root == null) {
            List<int> temp = new List<int>();
            temp.Add(0);
            temp.Add(0);
            return temp;
        }
        List<int> left = max_sum(root.left);
        List<int> right = max_sum(root.right);
        int no_root_l = left[0], root_l = left[1];
        int no_root_r = right[0], root_r = right[1];
 
        int root_sum_max = Math.Max(
            Math.Max(root.data, root.data + no_root_l),
            Math.Max(root.data + no_root_r,
                     root.data + no_root_r + no_root_l));
 
        int no_root_sum_max = Math.Max(
            Math.Max(root_l, root_r),
            Math.Max(Math.Max(root_l + root_r,
                              no_root_l + no_root_r),
                     Math.Max(root_l + no_root_r,
                              root_r + no_root_l)));
 
        List<int> ans = new List<int>();
        ans.Add(no_root_sum_max);
        ans.Add(root_sum_max);
        return ans;
    }
 
    public static int getMaxSum(Node root)
    {
 
        List<int> ans = max_sum(root);
        return Math.Max(ans[0], ans[1]);
    }
}
 
// This code is contributed by Tapesh(tapeshdua420)


Javascript




<script>
 
// JavaScript code to implement the approach
 
class Node{
    constructor(val){
        this.data = val
        this.left = null
        this.right = null
    }
}
 
 
class Solution{
 
    max_sum(root){
        if(root == null)
            return 0, 0
 
        let no_root_l, root_l = this.max_sum(root.left)
        let no_root_r, root_r = this.max_sum(root.right)
 
        let root_sum_max = Math.max(root.data, root.data+no_root_l,
                        root.data+no_root_r, root.data+no_root_r+no_root_l)
        let no_root_sum_max = Math.max(root_l, root_r, root_l + root_r, no_root_l+no_root_r,
                            root_l + no_root_r, root_r + no_root_l)
 
        return no_root_sum_max, root_sum_max
    }
 
    getMaxSum(root){
        return Math.max(this.max_sum(root))
    }
}
 
// This code is contributed by shinjanpatra
 
</script>


Output

21

Time Complexity: O(N)
Auxiliary Space: O(N)

This method is contributed by Thatikonda Aditya.

The maximum sum of nodes in a Binary tree such that no two are adjacent using Memorization:

To solve the problem follow the below idea:

For every node, we can either choose it or leave it and pass on this information to children. Since we are passing on this information about the parent being selected or not, we don’t need to worry about the grandchildren of the node

So for every node, we do the following:

  • If the parent is selected, we don’t select the current node and move on to the children.
  • if the parent is not selected, we will either select or not select this node; in either case, we pass that info to the children

Below is the implementation of the above approach:

C++




// C++ program to find maximum sum from a subset of
// non-adjacent nodes of binary tree
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node structure */
struct Node {
    int data;
    struct Node *left, *right;
};
 
/* Utility function to create a new Binary Tree node */
struct Node* newNode(int data)
{
    struct Node* temp = new struct Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Declaration of the vector to store the answer
vector<vector<int> > dp;
 
// Variables and function to index the given Binary tree
// This indexing will be used in dp
int cnt = 0;
Node* temp;
Node* giveIndex(Node* root)
{
    if (root == NULL)
        return NULL;
    // give the index to the current node and increment the
    // index for next nodes.
    Node* newNode1 = newNode(cnt++);
 
    // Recursively calling right and left subtree
    newNode1->left = giveIndex(root->left);
    newNode1->right = giveIndex(root->right);
    return newNode1;
}
 
// Memoization function to store the answer
int solve(Node* root, int b, Node* temp)
{
    if (root == NULL)
        return 0;
    // If the answer is already calculated return that
    // answer
    if (dp[temp->data][b] != -1)
        return dp[temp->data][b];
 
    // Variable to store the answer for the current node.
    int res;
 
    // if the parent is not selected then we can either
    // select ot not select this node.
    if (b == 0)
        res = max(root->data
                      + solve(root->right, 1, temp->right)
                      + solve(root->left, 1, temp->left),
                  solve(root->right, 0, temp->right)
                      + solve(root->left, 0, temp->left));
 
    // If parent is selected then we can't select this node.
    else
        res = solve(root->right, 0, temp->right)
              + solve(root->left, 0, temp->left);
 
    // return the answer
    return dp[temp->data][b] = res;
}
int getMaxSum(Node* root)
{
    // Initialization of the dp
    dp = vector<vector<int> >(100, vector<int>(2, -1));
    // Calling the indexing function
    temp = giveIndex(root);
    // calling the solve function for root with parent not
    // selected
    int res = solve(root, 0, temp);
 
    return res;
}
 
//  Driver code to test above methods
int main()
{
    // TEST 1
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->left->left = newNode(1);
    cout << getMaxSum(root) << endl;
 
    // TEST 2
    Node* root2 = newNode(10);
    root2->left = newNode(1);
    root2->left->left = newNode(2);
    root2->left->left->left = newNode(1);
    root2->left->right = newNode(3);
    root2->left->right->left = newNode(4);
    root2->left->right->right = newNode(5);
    cout << getMaxSum(root2);
 
    return 0;
}
// Code contributed by Anirudh Singh.


Java




// Java program to find maximum sum from a subset of
// non-adjacent nodes of binary tree
 
import java.util.HashMap;
 
/* A binary tree node structure */
class Node {
    int data;
    Node left, right;
    Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
class gfg {
    // Declaration of the vector to store the answer
    static int[][] dp;
 
    // Variables and function to index the given Binary tree
    // This indexing will be used in dp
    static int cnt = 0;
    static Node temp;
    static Node giveIndex(Node root)
    {
        if (root == null)
            return null;
        // give the index to the current node and increment
        // the index for next nodes.
        Node newNode1 = new Node(cnt++);
 
        // Recursively calling right and left subtree
        newNode1.left = giveIndex(root.left);
        newNode1.right = giveIndex(root.right);
        return newNode1;
    }
 
    // Memoization function to store the answer
    static int solve(Node root, int b, Node temp)
    {
        if (root == null)
            return 0;
        // If the answer is already calculated return that
        // answer
        if (dp[temp.data][b] != -1)
            return dp[temp.data][b];
 
        // Variable to store the answer for the current
        // node.
        int res;
 
        // if the parent is not selected then we can either
        // select ot not select this node.
        if (b == 0)
            res = Math.max(
                root.data + solve(root.right, 1, temp.right)
                    + solve(root.left, 1, temp.left),
                solve(root.right, 0, temp.right)
                    + solve(root.left, 0, temp.left));
 
        // If parent is selected then we can't select this
        // node.
        else
            res = solve(root.right, 0, temp.right)
                  + solve(root.left, 0, temp.left);
 
        // return the answer
        return dp[temp.data][b] = res;
    }
    static int getMaxSum(Node root)
    {
        // Initialization of the dp
        dp = new int[100][2];
        for (int i = 0; i < 100; i++) {
            dp[i][0] = -1;
            dp[i][1] = -1;
        }
        // Calling the indexing function
        temp = giveIndex(root);
        // calling the solve function for root with parent
        // not selected
        int res = solve(root, 0, temp);
 
        return res;
    }
 
      // Driver code
    public static void main(String args[])
    {
        // TEST 1
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(4);
        root.right.right = new Node(5);
        root.left.left = new Node(1);
        System.out.println(getMaxSum(root));
 
        // TEST 2
        Node root2 = new Node(10);
        root2.left = new Node(1);
        root2.left.left = new Node(2);
        root2.left.left.left = new Node(1);
        root2.left.right = new Node(3);
        root2.left.right.left = new Node(4);
        root2.left.right.right = new Node(5);
        System.out.print(getMaxSum(root2));
    }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)


Python3




# Python3 program to find maximum sum from a subset of
# non-adjacent nodes of binary tree
 
# A binary tree node structure
 
 
class newNode:
 
    def __init__(self, data):
 
        self.data = data
        self.left = None
        self.right = None
 
 
dp = [[]]
 
# Variables and function to index the given Binary tree
# This indexing will be used in dp
cnt = 0
temp = newNode(0)
 
 
def giveIndex(root):
 
    if (root == None):
        return None
    # give the index to the current node and increment the index for next nodes.
    global cnt
    cnt += 1
    newNode1 = newNode(cnt)
 
    # Recursively calling right and left subtree
    newNode1.left = giveIndex(root.left)
    newNode1.right = giveIndex(root.right)
    return newNode1
 
 
# Memoization function to store the answer
def solve(root, b, temp):
 
    if (root == None):
        return 0
    # If the answer is already calculated return that answer
    if (dp[temp.data][b] != -1):
        return dp[temp.data][b]
 
    # Variable to store the answer for the current node.
    res = 0
 
    # if the parent is not selected then we can either select ot not select this node.
    if (b == 0):
        res = max(root.data + solve(root.right, 1, temp.right) + solve(root.left, 1,
                                                                       temp.left), solve(root.right, 0, temp.right) + solve(root.left, 0, temp.left))
 
    # If parent is selected then we can't select this node.
    else:
        res = solve(root.right, 0, temp.right) + solve(root.left, 0, temp.left)
 
    # return the answer
    dp[temp.data][b] = res
    return res
 
 
def getMaxSum(root):
 
    # Initialization of the dp
    global dp
    dp = [[-1 for x in range(2)] for x in range(100)]
    # Calling the indexing function
    temp = giveIndex(root)
    # calling the solve function for root with parent not selected
    res = solve(root, 0, temp)
 
    return res
 
 
# Driver code
if __name__ == "__main__":
 
    # TEST 1
    root = newNode(1)
    root.left = newNode(2)
    root.right = newNode(3)
    root.right.left = newNode(4)
    root.right.right = newNode(5)
    root.left.left = newNode(1)
    print(getMaxSum(root))
 
    # TEST 2
    root2 = newNode(10)
    root2.left = newNode(1)
    root2.left.left = newNode(2)
    root2.left.left.left = newNode(1)
    root2.left.right = newNode(3)
    root2.left.right.left = newNode(4)
    root2.left.right.right = newNode(5)
    print(getMaxSum(root2))
 
# This code is contributed by Abhijeet Kumar(abhijeet19403)


C#




// C# program to find maximum sum from a subset of
// non-adjacent nodes of binary tree
 
using System;
using System.Collections.Generic;
 
/* A binary tree node structure */
public class Node {
    public int data;
    public Node left, right;
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
};
 
class gfg {
    // Declaration of the vector to store the answer
    static int[, ] dp;
 
    // Variables and function to index the given Binary tree
    // This indexing will be used in dp
    static int cnt = 0;
    static Node temp;
    static Node giveIndex(Node root)
    {
        if (root == null)
            return null;
        // give the index to the current node and increment
        // the index for next nodes.
        Node newNode1 = new Node(cnt++);
 
        // Recursively calling right and left subtree
        newNode1.left = giveIndex(root.left);
        newNode1.right = giveIndex(root.right);
        return newNode1;
    }
 
    // Memoization function to store the answer
    static int solve(Node root, int b, Node temp)
    {
        if (root == null)
            return 0;
        // If the answer is already calculated return that
        // answer
        if (dp[temp.data, b] != -1)
            return dp[temp.data, b];
 
        // Variable to store the answer for the current
        // node.
        int res;
 
        // if the parent is not selected then we can either
        // select ot not select this node.
        if (b == 0)
            res = Math.Max(
                root.data + solve(root.right, 1, temp.right)
                    + solve(root.left, 1, temp.left),
                solve(root.right, 0, temp.right)
                    + solve(root.left, 0, temp.left));
 
        // If parent is selected then we can't select this
        // node.
        else
            res = solve(root.right, 0, temp.right)
                  + solve(root.left, 0, temp.left);
 
        // return the answer
        return dp[temp.data, b] = res;
    }
    static int getMaxSum(Node root)
    {
        // Initialization of the dp
        dp = new int[100, 2];
        for (int i = 0; i < 100; i++) {
            dp[i, 0] = -1;
            dp[i, 1] = -1;
        }
        // Calling the indexing function
        temp = giveIndex(root);
        // calling the solve function for root with parent
        // not selected
        int res = solve(root, 0, temp);
 
        return res;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        // TEST 1
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(4);
        root.right.right = new Node(5);
        root.left.left = new Node(1);
        Console.WriteLine(getMaxSum(root));
 
        // TEST 2
        Node root2 = new Node(10);
        root2.left = new Node(1);
        root2.left.left = new Node(2);
        root2.left.left.left = new Node(1);
        root2.left.right = new Node(3);
        root2.left.right.left = new Node(4);
        root2.left.right.right = new Node(5);
        Console.Write(getMaxSum(root2));
    }
}
 
// This code has been contributed by Abhijeet
// Kumar(abhijeet19403)


Javascript




// JavaScript program to find maximum sum from a
    // subset of non-adjacent nodes of binary tree
 
    class Node{
        constructor(val){
            this.data = val
            this.left = null
            this.right = null
        }
    }
     
    // Variables and function to index the given Binary tree
    // This indexing will be used in dp
    var temp;
    var cnt = 0;
     
    // Declaration of the vector to store the answer
    var dp = new Array(100);
    // Initialization of the dp
    for(let i=0;i<100;i++){
        dp[i] = new Array(2);
    }
     
    function giveIndex(root){
        if(root==null){
            return null;
        }
        // give the index to the current node and increment
        // the index for next nodes.
        var newNode1 = new Node(cnt++);
         
        // Recursively calling right and left subtree
        newNode1.left = giveIndex(root.left);
        newNode1.right = giveIndex(root.right);
        return newNode1;
    }
     
    // Memoization function to store the answer
    function solve(root, b, temp){
        if(root==null){
            return null;
        }
         
        // If the answer is already calculated
        // return that answer
        if(dp[temp.data][b]!=-1){
            return dp[temp.data][b];
        }
         
        // Variable to store the answer
        // for the current node.
        var res;
         
        // if the parent is not selected then we can either
        // select ot not select this node.
        if(b==0){
            res = Math.max(root.data + solve(root.right, 1, temp.right)
                       + solve(root.left, 1, temp.left),
                solve(root.right, 0, temp.right)
                    + solve(root.left, 0, temp.left));
        }
         
        // If parent is selected then we can't select this
        // node.
        else{
            res = solve(root.right, 0, temp.right)
                  + solve(root.left, 0, temp.left);
        }
         
        dp[temp.data][b] = res;
         
        // return the answer
        return dp[temp.data][b];
    }
     
    function getMaxSum(root){
        for(let i=0;i<100;i++){
            dp[i][0] = -1;
            dp[i][1] = -1;
        }
         
        // Calling the indexing function
        temp = giveIndex(root);
         
        // calling the solve function for root with parent
        // not selected
        var res = solve(root, 0, temp);
         
        return res;
    }
     
    // TEST 1
    var root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.right.left = new Node(4);
    root.right.right = new Node(5);
    root.left.left = new Node(1);
    document.write(getMaxSum(root)+"<br>");
     
    // TEST 2
    var root2 = new Node(10);
    root2.left = new Node(1);
    root2.left.left = new Node(2);
    root2.left.left.left = new Node(1);
    root2.left.right = new Node(3);
    root2.left.right.left = new Node(4);
    root2.left.right.right = new Node(5);
    document.write(getMaxSum(root2));
     
    // This code is contributed by lokesh.


Output

11
21

Time Complexity: O(N)
Auxiliary Space: O(N)

This method and implementation is contributed by Anirudh Singh.

Memorization



Previous Article
Next Article

Similar Reads

Maximum sum of nodes in Binary tree such that no two are adjacent | Dynamic Programming
Given a N-ary tree with a value associated with each node, the task is to choose a subset of these nodes such that sum of chosen nodes is maximum under a constraint that no two chosen node in subset should be directly connected that is, if we have taken a node in our sum then we can’t take its any children in consideration and vice versa.Examples:
9 min read
Shortest path length between two given nodes such that adjacent nodes are at bit difference 2
Given an unweighted and undirected graph consisting of N nodes and two integers a and b. The edge between any two nodes exists only if the bit difference between them is 2, the task is to find the length of the shortest path between the nodes a and b. If a path does not exist between the nodes a and b, then print -1. Examples: Input: N = 15, a = 15
7 min read
Maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST
Given a binary tree, the task is to print the maximum sum of nodes of a sub-tree which is also a Binary Search Tree.Examples: Input : 7 / \ 12 2 / \ \ 11 13 5 / / \ 2 1 38 Output:44 BST rooted under node 5 has the maximum sum 5 / \ 1 38 Input: 5 / \ 9 2 / \ 6 3 / \ 8 7 Output: 8 Here each leaf node represents a binary search tree also a BST with su
12 min read
Find a set of at most N/2 nodes from a Graph such that all remaining nodes are directly connected to one of the chosen nodes
Given an integer N, representing the number of nodes present in an undirected graph, with each node valued from 1 to N, and a 2D array Edges[][], representing the pair of vertices connected by an edge, the task is to find a set of at most N/2 nodes such that nodes that are not present in the set, are connected adjacent to any one of the nodes prese
12 min read
Count of nodes in given N-ary tree such that their subtree is a Binary Tree
Given an N-ary tree root, the task is to find the count of nodes such that their subtree is a binary tree. Example: Input: Tree in the image below Output: 11Explanation: The nodes such that there subtree is a binary tree are {2, 8, 10, 6, 7, 3, 1, 9, 5, 11, 12}. Input: Tree in the image below Output: 9 Approach: The given problem can be solved by u
11 min read
Sum of nodes in a binary tree having only the left child nodes
Given a binary tree, the task is to find the sum of binary tree nodes having only the left child nodes. Example: Input: 8 / \ 3 7 / \ / 5 6 0 / / 1 2Output: 18 Explanation: Nodes with values 5, 6, and 7 are the ones that have only the left child nodes Input: 2 / \ 3 1 / / 5 6Output: 4 Approach: The given problem can be solved by traversing the bina
6 min read
Maximum sum in circular array such that no two elements are adjacent
Given a circular array containing of positive integers value. The task is to find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. Examples: Input: circular arr = {1, 2, 3, 1} Output : 4 subsequence will be(1, 3), hence 1 + 3 = 4 Input: circular arr = {1, 2, 3, 4, 5, 1} Output:
15+ min read
Maximum sub-sequence sum such that indices of any two adjacent elements differs at least by 3
Given an array arr[] of integers, the task is to find the maximum sum of any sub-sequence in the array such that any two adjacent elements in the selected sequence have at least a difference of 3 in their indices in the given array. In other words, if you select arr[i] then the next element you can select is arr[i + 3], arr[i + 4], and so on... but
12 min read
Maximum sum such that exactly half of the elements are selected and no two adjacent
Given an array A containing N integers. Find the maximum sum possible such that exact floor(N/2) elements are selected and no two selected elements are adjacent to each other. (if N = 5, then exactly 2 elements should be selected as floor(5/2) = 2) For a simpler version of this problem check out this. Examples: Input: A = [1, 2, 3, 4, 5, 6] Output:
14 min read
Maximum sum in circular array such that no two elements are adjacent | Set 2
Given an array arr[] of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array where the last and the first elements are assumed adjacent. Examples: Input: arr[] = {3, 5, 3} Output: 5 Explanation: We cannot take the first and last elements because they are consid
13 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg