Katkat
Back

Maximize sum with no adjacent tree nodes

AirbnbSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use tree-based dynamic programming to solve an optimization challenge where you must select a subset of nodes with no two being adjacent, while maximizing the sum of their values.

Problem Statement

You are given a binary tree where each node contains an integer value. Your task is to find the maximum possible sum of a subset of nodes such that no two selected nodes are adjacent (i.e., you cannot select a child if its parent is selected).

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_independent_set_sum(root: TreeNode) -> int:
    pass

Examples

Example 1: Input: root = [10, 5, 15, 1, 8, null, 7]

  • Root 10 has children 5 and 15.
  • Node 5 has children 1 and 8.
  • Node 15 has child 7.
  • Output: 25
  • Explanation: Select nodes 10 and 15 (cannot select 5 or 8, but we can't select 10 and 15 anyway as they are adjacent; select 10, 1, 8, 7 is invalid; max is 10 + 8 + 7 = 25).

Example 2: Input: root = [3, 4, 5, 1, 3, null, 1]

  • Output: 9
  • Explanation: Select nodes 4 and 5 (sum 9).

Constraints

  • The number of nodes in the tree is in the range [0, 10,000].
  • Node values are between -1,000 and 1,000.
  • The tree is guaranteed to be a valid binary tree.

Hints

Hint 1

Consider defining a state for each node that returns two values: the maximum sum including the node and the maximum sum excluding the node.

Hint 2

If you include the current node, you must exclude its immediate children; if you exclude the current node, you can choose to either include or exclude its children.

Hint 3

Use a post-order traversal to compute these values bottom-up, as the result for a parent depends on the results of its children.

Follow-up questions

  • How would you modify your solution if the graph were an N-ary tree instead of a binary tree?
  • What if each node also had a 'weight' multiplier that changed depending on the depth of the node?
  • How does the time and space complexity of your solution change if the tree is skewed into a linked list?