VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 10: Trees and BSTs

Lesson 10.12 of 14 in this module Unrolled Pro

Binary Tree Maximum Path Sum

The largest sum of node values along any path in a binary tree, where values can be negative. From trying every pair of endpoints (O(n²) paths, each summed), to computing, at every node, the best downward arm on each side from scratch, to one post-order pass that returns the best arm (dropping negative arms) and records node + left arm + right arm. Then paths that must start at the root or end at a leaf, recovering the path, all-negative trees, and the ML version: the highest-scoring chain in a tree of scored decisions.

about 10 min 4 Python examples 2 quick checks

Problem. A path is a sequence of nodes where each adjacent pair is connected by an edge, with no node repeated; it doesn't have to pass through the root, and it has at least one node. Return the maximum sum of node values over all paths. Values can be negative.

text
     -10
     /  \
    9    20            →   42     (15 → 20 → 7)
        /  \
       15   7

  -3                   →   -3     (a single node; every path must have one)

It's lesson 10.5's diameter with values instead of edge counts. The new twist is negativity: an arm that sums to less than zero should be dropped, not extended, and an all-negative tree still has to return its best single node.

ML context. Picture a tree of decisions where each node carries a score (a log-probability, a reward, a gain minus a cost), and you want the best-scoring chain: the most likely chain of hierarchical labels, the most profitable sequence of follow-up actions, the strongest chain of evidence through a tree of retrieved documents. Negative scores are exactly the "don't go there" signal this problem handles (Change D).


1. Step 1: Clarify

That's the preview. Modules 00–01 are free; this lesson is part of Unrolled Pro.
Staff AI & Pro Tier Lesson

Unlock "Binary Tree Maximum Path Sum"

The foundations are free forever. Unrolled Pro unlocks the complete lesson, production architectures, and 55 battle-tested ML system design case studies.

Everything included with Pro:
All 234+ Deep-Dive Lessons across transformer internals, inference, RAG & agents
55 Staff-Level ML & System Design Case Studies with mathematical capacity estimates
AI Engineer Sheet & Exercises with worked solutions, self-checks, and code
100 Landmark Research Papers guided walkthroughs & progress tracking
14-Day Money-Back Guarantee — 100% full refund if you aren't satisfied
View Plans & Unlock All Lessons

From ₹167/mo (~$2/mo) · Cancel anytime · Instant activation

100% Risk-Free: 14-day no-questions-asked money-back guarantee