Part A — Leaves are the only“alive”nodes
You are given a binary tree whose nodes have integer values.
Define an alive node as a leaf node.
Find the maximum path sum between any two alive nodes in the tree.
A path is a sequence of connected nodes; its sum is the sum of node values along the path.
Return the maximum possible sum among all paths whose two endpoints are alive nodes.
Part B (Follow-up) — Internal nodes can also be“alive”
Now some non-leaf nodes may also be marked as alive (e.g., denoted by an asterisk in the example).
Find the maximum path sum between any two alive nodes subject to the constraint:
- Along the chosen path, the only alive nodes are its two endpoints (i.e., no other alive node is allowed in between).
Return the maximum possible sum under this rule.
Example (informal):
If the alive nodes are {100*, 2*, 50*, 15*, 4*} and the best path is 100* → 2* → 50*, the answer is 100 + 2 + 50 = 152.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Doordash, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Tiktok or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
