Box Office Override Staffing
Maximum sum of binary tree node values with at most one adjacent chosen pair
A theater's box-office desks are organized as a binary tree. Each node represents a desk, and its value is the net benefit of staffing that desk for an evening. Benefits may be negative because some desks cost more to operate than they bring in.
Normally, a desk and its direct parent cannot both be staffed because they share a secure terminal connection. The theater has one override device, allowing at most one parent-child connection to have both endpoint desks staffed.
Choose any subset of desks such that at most one tree edge has both endpoints chosen. Return the maximum possible sum of the chosen desks' values.
The restriction applies only to direct parent-child connections. Siblings and more distant relatives do not conflict. You may choose no desks, and you do not have to use the override. An empty tree has total benefit zero.
Examples
Example 1
Input: root = [8,7,6] Output: 15
The root has two child desks. Staffing all three would require two overrides, so it is forbidden. Compare staffing both children with staffing the root and just one child.
Example 2
Input: root = [4,-3,5,8,2,null,7] Output: 22
The negative-benefit desk can be skipped without preventing its descendants from being staffed. One useful arrangement staffs both children of that desk and uses the override on the connection between the right-side desk and its child.
Example 3
Input: root = [] Output: 0
There are no desks, so the only available choice is the empty subset.
Constraints
- The tree contains between 0 and 3,000 nodes.
- -10,000 <= node.val <= 10,000.
- The input is a binary tree, not necessarily balanced or a binary search tree.
The intended solution takes O(n) time and O(n) auxiliary space. An iterative traversal avoids recursion-depth issues on a long chain.
Hints
Show hint 1Hint 1
For each subtree, distinguish whether its root is staffed and whether an override has already been used inside that subtree.
Show hint 2Hint 2
When combining a child subtree, add one to the override count exactly when both the parent and child roots are staffed. Discard combinations whose total exceeds one.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you generalize the solution to allow at most k overridden connections, and what would its time complexity be?
- How could you reconstruct one optimal set of desks, identifying each desk by its path from the root?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem