Best-value path anywhere in a decision tree

Question

Each node of a binary tree carries a value (which can be negative). A path is any sequence of connected nodes that goes through each node at most once; it may start and end anywhere and may bend at a node (using both children). Find the maximum possible sum along any path.

        -10
        /  \
       9    20
           /  \
          15   7
-> 42       # 15 -> 20 -> 7

Return the maximum path sum. The best path need not touch the root.

Accepted Answer

For each node compute the best "downward gain" it can contribute: its own value plus the larger of its two children's gains, but never less than the node alone (a negative child is dropped by clamping at 0). While doing so, a full path bending at this node equals node.val + leftgain + rightgain; track the best such value globally. Tracing the example: at node 20, left=15 and right=7, so the bending path 15+20+7 = 42 sets the best; the negative root cannot improve it. Time O(n), space O(h) for recursion (h = tree height). Edge cases: all-negative trees return the single largest (least negative…

Best-value path anywhere in a decision tree

Your answer

More Coding questions