DoorDash VO: Max Path Sum Between Two Alive Nodes

This article is organized by oavoservice in an interview review style: providing problem clarification, practical state definitions, edge case handling, and writeable code templates.

Problem (Restated)

Given a binary tree where each node has an integer weight.

• Part A: Define "alive nodes" as leaf nodes. Find the maximum path sum between any two alive nodes.
• Part B (Follow-up): Some internal nodes may also be alive. The requirement is that the path endpoints must be alive, and no other alive nodes can appear in the middle of the path. Find the maximum path sum.

The path must be continuous along parent-child pointers.

Interview Clarifications

• Path must be a simple path on the tree (no repeated nodes).
• Is it allowed to select only one node? Usually, "two endpoints are alive" is required, so at least two endpoints must be selected.
• Node weights can be negative.

Part A: Alive = Leaf Nodes

This is a variant of the classic "Maximum Path Sum", but endpoints must be leaves.

Idea

Post-order DFS, returning:

• down[u]: Maximum path sum from u down to some leaf (must end at a leaf).

At u, if both left and right subtrees exist (can provide leaves), then we can update the global answer (leaf to leaf) with down[left] + val[u] + down[right].

Complexity

• Time: O(n)
• Space: O(h) recursion stack (h is tree height)

Python Code Template

from math import inf

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def max_leaf_to_leaf_sum(root: TreeNode) -> int:
    ans = -inf

    def dfs(node: TreeNode) -> int:
        nonlocal ans
        if not node:
            return -inf

        # Leaf: down is itself
        if not node.left and not node.right:
            return node.val

        left_down = dfs(node.left) if node.left else -inf
        right_down = dfs(node.right) if node.right else -inf

        # If both sides have leaf paths, can form leaf-leaf
        if node.left and node.right:
            ans = max(ans, left_down + node.val + right_down)

        # down must go to the existing side
        return node.val + max(left_down, right_down)

    down_root = dfs(root)

    # If the whole tree cannot form leaf-leaf (e.g. linked list tree), usually agree on returning down_root or error.
    # Here choice: if ans not updated, return down_root (max sum from root to some leaf).
    return ans if ans != -inf else down_root

Part B: Internal Nodes Can Be Alive (No Alive Nodes in Middle)

The key here is: Path must encounter alive nodes at both ends, and cannot pass through alive nodes in the middle.

State Design (Extensible)

Post-order DFS, returning two types of info for each node:

• best_end[u]: "Best downward path sum" from u to an alive node in the subtree, but this downward path (excluding the endpoint alive) does not contain other alive nodes.
• is_alive[u]: Whether the current node is alive.

Transitions:

• If u itself is alive, then best_end[u] = val[u], and cannot continue downwards (because intermediate nodes cannot be alive).
• If u is not alive, it can connect to best_end of left/right subtrees.
• Way to form answer: At a node u, combine two alive endpoint paths from left and right subtrees through u: left_best + val[u] + right_best.

Code Template (Alive Set as Input)

from math import inf


def max_alive_to_alive_sum(root: TreeNode, alive: set[TreeNode]) -> int:
    ans = -inf

    def dfs(node: TreeNode) -> int:
        nonlocal ans
        if not node:
            return -inf

        node_is_alive = node in alive

        left_best = dfs(node.left)
        right_best = dfs(node.right)

        # If current node is alive: it can only be an endpoint, not a "middle" continuing downwards
        if node_is_alive:
            ans = max(ans, node.val)  # Allow both endpoints to be same point? Adjust as needed
            return node.val

        # Current node is not alive: can carry up alive endpoints from subtree
        best_end = node.val + max(left_best, right_best)

        # If both sides can provide alive endpoints, form alive->alive here
        if left_best != -inf and right_best != -inf:
            ans = max(ans, left_best + node.val + right_best)

        return best_end

    dfs(root)
    return ans

Common Interview Follow-ups

• Why is -inf better than None? (Easier for max/comparison)
• What to return if a chain tree cannot form leaf-leaf? Align with interviewer beforehand.
• When node values are negative, why can't we discard subpaths arbitrarily? (Endpoint constraints force path selection).

If you are preparing for VO at DoorDash / Snowflake / Google, oavoservice will train you to articulate state definitions and boundaries for these "classic variant constraints" within 5 minutes.

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.