A Party Without Direct Bosses

Medium

A company's structure is a binary tree: the director sits at root, and every employee has at most two direct reports. A node's value tells how much that person livens up the office party. Nobody wants to party next to their *direct* boss, so an employee and their immediate manager may not both be invited. A boss's boss is fine. Return the largest total liveliness you can get by choosing the guest list.

Example 1

root=tree_node([5, 1, 2, 4, 6, None, 3]) → 18

The best choice is 4, 6 and 3 (their bosses 1 and 2 stay home) plus the director 5: 5 + 4 + 6 + 3 = 18.

Example 2

root=tree_node([2, 9, None, 1, 1]) → 9

The employee worth 9 outweighs everyone else combined: the director plus both of 9's reports give only 2 + 1 + 1 = 4 < 9.

Example 3

root=tree_node([7]) → 7

Constraints

The tree has between 1 and 10⁴ nodes
0 ≤ Node.val ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Dynamic Programming Binary Tree

Similar problems

Biggest Search Subtree Medium Zigzag Tree Descent Medium Heaviest Path in a Tree Hard Fewest Guards on a Tree Hard Heaviest Search Subtree Hard

Input

root=tree_node([5, 1, 2, 4, 6, None, 3])

Expected

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.