Binary Tree Max Without Adjacent | Dataford Interview Questions

Maximum sum of nodes in a binary tree such that no two are adjacent.

Asked in the DSA stage. Given as a second problem in the last 10 minutes.

Input and Output

Implement max_non_adjacent_sum(root), where root is the root of a binary tree whose nodes have integer val, left, and right fields. Return the maximum sum of selected node values. Selecting neither a node nor any of its descendants is allowed. Test cases represent trees in level-order arrays, using null for missing children.

Constraints

0 <= number of nodes <= 10^4
-10^4 <= node.val <= 10^4
The input is a valid binary tree
Selecting no nodes is allowed

Function Signature

def max_non_adjacent_sum(root):

Your question is Binary Tree Max Without Adjacent. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem