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

Problem Statement

Given a binary tree with a value associated with each node, find the maximum sum of nodes such that no two adjacent nodes (parent-child) are included in the sum.

Example:

Note: If we include a node, we cannot include its parent or children.

Approach 1: Brute Force (Recursion with Include/Exclude)

Intuition

For each node, we have two choices: include it or exclude it. If we include it, we cannot include its children but can include grandchildren. If we exclude it, we can consider including children.

Algorithm

1. For each node, calculate two values:
   • Include: node.val + exclude(left) + exclude(right)
   • Exclude: max(include, exclude) of left + max(include, exclude) of right
2. Recursively compute for all nodes
3. Return max(include_root, exclude_root)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Returns max sum when node is included
    private int robInclude(TreeNode root) {
        if (root == null) return 0;
        
        int sum = root.val;
        
        // Skip children, add grandchildren
        if (root.left != null) {
            sum += robExclude(root.left);
        }
        if (root.right != null) {
            sum += robExclude(root.right);
        }
        
        return sum;
    }
    
    // Returns max sum when node is excluded
    private int robExclude(TreeNode root) {
        if (root == null) return 0;
        
        // For each child, take max of include or exclude
        return Math.max(robInclude(root.left), robExclude(root.left)) +
               Math.max(robInclude(root.right), robExclude(root.right));
    }
    
    public int maxSumNoAdjacent(TreeNode root) {
        return Math.max(robInclude(root), robExclude(root));
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Exponential due to overlapping subproblems
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Optimal (DP with Pair Return)

Intuition

Instead of separate include/exclude functions, return a pair from each recursive call containing both values. This avoids recomputation and solves in a single traversal.

Algorithm

1. For each node, return pair: (include_sum, exclude_sum)
2. Include: node.val + left.exclude + right.exclude
3. Exclude: max(left.include, left.exclude) + max(right.include, right.exclude)
4. Final answer: max(root.include, root.exclude)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    // Returns int[]{include_sum, exclude_sum}
    private int[] solve(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        
        int[] left = solve(root.left);
        int[] right = solve(root.right);
        
        // If we include this node, we cannot include children
        int include = root.val + left[1] + right[1];
        
        // If we exclude this node, take max of include/exclude for each child
        int exclude = Math.max(left[0], left[1]) + 
                      Math.max(right[0], right[1]);
        
        return new int[]{include, exclude};
    }
    
    public int maxSumNoAdjacent(TreeNode root) {
        int[] result = solve(root);
        return Math.max(result[0], result[1]);
    }
}

With Memoization (Alternative)

Complexity Analysis

• Time Complexity: O(n) - Each node is visited exactly once
• Space Complexity: O(n) - Recursion stack + memoization storage (or just O(h) for pair approach)

Key Takeaways

1. Include/Exclude pattern: Classic DP pattern for non-adjacent selection
2. Pair return optimization: Return both states to avoid recomputation
3. Similar to House Robber problem but on tree structure
4. Key formula:
   • Include = node.val + exclude(left) + exclude(right)
   • Exclude = max(include, exclude) of each child
5. This is Tree DP - DP on tree structure using postorder traversal