How should I practice Maximum Sum of Non-Adjacent Tree Nodes?

Start by reading the full statement, solve the visible examples, then compare the pattern against related InMobi onsite interview problems in FastPrep.

Is Maximum Sum of Non-Adjacent Tree Nodes associated with InMobi?

FastPrep tags this as a InMobi onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Maximum Sum of Non-Adjacent Tree Nodes

Learn this problem

● Medium

InMobiFULLTIMEONSITE INTERVIEW

Problem statement

Given the root root of a binary tree with integer node values, choose a set of nodes with maximum possible total value.

No two chosen nodes may be adjacent: if a node is chosen, neither of its children may be chosen. Selecting no nodes is allowed, so the answer is 0 for an empty tree or when every nonempty valid selection has a negative sum.

Return the maximum sum.

Function

maxNonAdjacentSum(root: TreeNode) → long

Examples

Example 1

root = [10,1,2]return = 10

Choosing only the root gives 10, which is larger than choosing both children for a total of 3.

Example 2

root = [1,2,3,1,null,4,5]return = 11

One optimal choice contains the root and the three grandchildren with values 1, 4, and 5, totaling 11.

Example 3

root = [-5,-2,-3]return = 0

Every node value is negative, so selecting no nodes gives the maximum sum 0.

Example 4

root = []return = 0

An empty tree contains no nodes, so its maximum selectable sum is 0.

Constraints

0 <= number of nodes <= 5 * 10^4
-10^9 <= node.val <= 10^9
The input is a valid binary tree.
The answer fits in a signed long.