Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Maximum Non-Adjacent Tree Sum

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return the maximum sum of the integers that can be obtained given no two integers can be adjacent parent to child.

Constraints
n ≤ 100,000 where n is the number of nodes in root
Example 1
Input

    1
   / \
  4   5
 / \
3   2

Output
10
Explanation
We can pick 3, 2 and 5. Note if we picked 4, we wouldn’t be able to pick 3 and 2 since they are adjacent.

Maximum Non-Adjacent Tree Sum via Recursion – Bottom Up Dynamic Programming Algorithm

For each Tree Node, we return two values, maximum value if we take current node, or if we don’t. Then, if we don’t take left and right, we can take current node, or if we don’t take current node, the maximum value can be computed by the sum of the values from left and right – taking or not taking respectively.

The values are computed recursively – from leaves upwards to the root i.e. Bottom-up Dynamic Programming Algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        def dfs(root):
            if not root:
                return 0, 0
            takeLeft, notTakeLeft = dfs(root.left)
            takeRight, notTakeRight = dfs(root.right)
            return root.val + notTakeLeft + notTakeRight, \
                   max(takeLeft, notTakeLeft) + max(takeRight, notTakeRight)
        a = dfs(root)
        return max(a[0], a[1])

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        def dfs(root):
            if not root:
                return 0, 0
            takeLeft, notTakeLeft = dfs(root.left)
            takeRight, notTakeRight = dfs(root.right)
            return root.val + notTakeLeft + notTakeRight, \
                   max(takeLeft, notTakeLeft) + max(takeRight, notTakeRight)
        a = dfs(root)
        return max(a[0], a[1])

Top Down Dynamic Programming Algorithm via Recursion with Memoziation to Compute the Maximum Non-Adjacent Tree Sum

We can solve this problem via Top Down Dynamic Programming Algorithm. For each node, if we don’t take it (passing a boolean parameter to indicate that we intend to take this node or not) – There are four combinations i.e. taking both left and right, taking either left or right, or don’t take at all.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        if root is None:
            return 0
        @cache
        def dfs(root, taken):
            if root is None:
                return 0
            if taken:
                return dfs(root.left, False) + dfs(root.right, False) + root.val
            return max(dfs(root.left, True) + dfs(root.right, True),\
                       dfs(root.left, False) + dfs(root.right, False),\
                       dfs(root.left, True) + dfs(root.right, False),\
                       dfs(root.left, False) + dfs(root.right, True))
        return max(dfs(root, False), dfs(root, True))

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        if root is None:
            return 0
        @cache
        def dfs(root, taken):
            if root is None:
                return 0
            if taken:
                return dfs(root.left, False) + dfs(root.right, False) + root.val
            return max(dfs(root.left, True) + dfs(root.right, True),\
                       dfs(root.left, False) + dfs(root.right, False),\
                       dfs(root.left, True) + dfs(root.right, False),\
                       dfs(root.left, False) + dfs(root.right, True))
        return max(dfs(root, False), dfs(root, True))

For Top Down DP, we have to apply memoization via cache to avoid calculation of duplicate function calls.

–EOF (The Ultimate Computing & Technology Blog) —