# 5 Best Ways to Program to Find Maximum Sum of Non Adjacent Nodes of a Tree in Python

Rate this post

π‘ Problem Formulation: We aim to solve a classic algorithmic challenge in Python: finding the maximum sum of non-adjacent nodes in a binary tree. Given a binary tree, we need to select a subset of nodes such that no two adjacent nodes (connected directly by an edge) are selected and the sum of the values of these nodes is maximized. For example, if we’re given a tree where the root node has a value of 10, and it has two children with values 5 and 7, choosing the root node and any of its children is invalid. The desired output is the largest possible sum following the rules.

## Method 1: Recursive Approach with Memoization

The first method involves a recursive function that traverses the tree and considers two scenarios: including or excluding the current node in the sum. Memoization is used to improve performance by storing the results of subproblems.

Here’s an example:

if root is None:
return 0
if memo is None:
memo = {}

if root in memo:
return memo[root]

include_root = root.value
if root.left:
if root.right:

memo[root] = max(include_root, exclude_root)
return memo[root]

Output: the maximum sum of non-adjacent nodes.

This recursive function takes a tree node as an argument and calculates the maximum sum while considering and ignoring its value. By storing already calculated sums in a dictionary (`memo`), we avoid re-calculating sums for the same nodes, which significantly increases the efficiency of our solution.

## Method 2: Dynamic Programming on Trees

Dynamic programming can be applied to trees by breaking down the problem into smaller subproblems. We compute the maximum sum for each subtree rooted at a node and use these results to compute the sum for larger trees.

Here’s an example:

def helper(node):
if not node:
return (0, 0)

left_pair = helper(node.left)
right_pair = helper(node.right)

return (node.value + left_pair[1] + right_pair[1],
max(left_pair[0], left_pair[1]) + max(right_pair[0], right_pair[1]))

return max(helper(root))

# Utility class to define a node
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

Output: the maximum sum of non-adjacent nodes.

This code defines a helper function that returns two values for each node: the maximum sum including that node, and the maximum sum excluding it. The `max_sum_non_adjacent` function then picks the optimal solution. This approach encapsulates the problem into smaller sub-tasks, making the dynamic programming solution intuitive and efficient.

## Method 3: Greedy Choice with Level Order Traversal

In this method, we employ a greedy algorithm alongside level order traversal to pick the best nodes to include. This approach, however, may not always yield the optimal result but can serve as a fast heuristic.

Here’s an example:

from collections import defaultdict, deque

if not root:
return 0

level_sum = defaultdict(int)
max_level = -1

queue = deque([(root, 0)])
while queue:
node, level = queue.popleft()
level_sum[level] += node.value
max_level = max(max_level, level)

if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))

even_sum = odd_sum = 0
for level in range(max_level+1):
if level % 2 == 0:
even_sum += level_sum[level]
else:
odd_sum += level_sum[level]

return max(even_sum, odd_sum)

Output: an estimation of the maximum sum of non-adjacent nodes or a heuristic answer if optimal answer is not reached.

This code snippet defines a function that uses breadth-first search to calculate the sum of values at each level of the tree. Although this method makes a greedy choice to maximize the sum, it doesn’t account for the scenario where non-adjacent nodes within the same level could result in a larger sum.

## Method 4: Optimized Dynamic Programming Approach

Optimized dynamic programming approach builds upon Method 2 by reducing the space complexity. Instead of storing values for each node, it operates in a bottom-up manner directly updating the node values.

Here’s an example:

def dfs(node):
if not node:
return (0, 0)

left_inc, left_exc = dfs(node.left)
right_inc, right_exc = dfs(node.right)

return (node.value + left_exc + right_exc,
max(left_inc, left_exc) + max(right_inc, right_exc))

return max(dfs(root))

# Assume Node is defined as in previous example

Output: the maximum sum of non-adjacent nodes.

This code uses a depth-first search (DFS) to visit nodes and calculate their values for the two states: included and excluded. It does not require additional storage for subproblems, thus optimizing space.

## Bonus One-Liner Method 5: Simplistic Recursive Function

As a bonus, a simplistic recursive function that doesn’t utilize memoization or dynamic programming might be used for smaller trees or for understanding the brute-force approach.

Here’s an example:

if not root: return 0
incl_root = root.value
if root.left:
if root.right: