Maximum Non-Adjacent Nodes Sum

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Maximum sum of non-adjacent nodes in binary tree. Each node: choose include or exclude.

Algorithm

1For each node: included = node.val + sum of grandchildren sums. Excluded = max children sums. Return max.

Common Pitfalls

•Same as LC 337 (House Robber III). Pair return: (includeMax, excludeMax). O(n) post-order traversal.

Maximum Non-Adjacent Nodes Sum.java

Java

// Approach: DP on tree. For each node: take = node.val + sum(skip children); skip = sum(max(take,skip) each child).
// Time: O(n) Space: O(n)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    private int getAns(Node root, HashMap<Node, Integer> dp) {
        if (root == null)
            return 0;
        if (dp.containsKey(root))
            return dp.get(root);
        int include = root.data;
        if (root.left != null)
            include += getAns(root.left.left, dp) + getAns(root.left.right, dp);
        if (root.right != null)
            include += getAns(root.right.left, dp) + getAns(root.right.right, dp);
        int exclude = getAns(root.left, dp) + getAns(root.right, dp);
        int ans = Math.max(include, exclude);
        dp.put(root, ans);
        return ans;
    }

    public int getMaxSum(Node root) {
        return getAns(root, new HashMap<>());
    }
}

Was this solution helpful?