parikshan

path-sum

Difficulty: Easy  ·  Topic: Trees  ·  Practice it on parikshan: /practice/path-sum/start

The story

A logistics platform models warehouse-to-customer routes as a tree, with the warehouse at the root, regional hubs as internal nodes, and customer addresses as leaves. Each edge carries a transit cost in rupees, captured on the parent node. When a customer requests "deliver this for exactly the budget I have" (a freight-broker negotiation where the warehouse cannot deliver above the budget and will not pay if below it because that means a competitor took a margin), the dispatcher needs to know whether some root-to-leaf path through the network costs exactly the target. They do not need the path itself, just yes or no, fast. This decision blocks the dispatch confirmation in the booking flow.

That is path-sum. Once you see this problem in this framing, you will recognise it in every "is there a root-to-leaf path that satisfies some additive constraint?" question: depth-aware billing in cloud platforms, capacity routing in CDNs, search frontiers in IDA* style game AI.

What's actually being asked

Given a binary tree and an integer target, decide whether some root-to-leaf path has values summing to target. A leaf is a node with no children. The empty tree has no root-to-leaf paths, so the answer is false for any target.

The naive approach

Enumerate every root-to-leaf path, sum each one, check against the target. That works, but if the tree has L leaves you do L walks of average length O(h), for O(L * h) work. A balanced tree has L = n/2 and h = log n, so it is O(n log n), fine. On a degenerate chain the cost shrinks to O(n) because there is only one path, but on a tree shaped like a balanced fan with deep tails you can hit the limit.

The other naive trap: build the list of all paths first, then check sums. That is O(n * h) memory and unnecessary.

The key insight

You do not need to enumerate paths. You can carry the remaining sum down the tree. At the root, the remaining target is target - root.val. At every step into a child, subtract that child's value. The question collapses to: "does there exist a leaf whose remaining (just before subtracting the leaf's own value) equals the leaf's value?" or equivalently "does the carry hit zero exactly at a leaf?".

The recursion is a textbook DFS with one extra parameter: a running remaining that updates as you descend. The base case is "leaf reached AND remaining is zero". Short-circuit on the first success.

Step-by-step approach

  1. Parse the level-order array into a tree. Parse the target on the second line.
  2. If the tree is empty, print false and exit. The empty tree has no root-to-leaf paths.
  3. Define hits(node, remaining):
    • If node is a leaf, return remaining == node.val.
    • Otherwise return (node.left and hits(node.left, remaining - node.val)) OR (node.right and hits(node.right, remaining - node.val)).
  4. Print hits(root, target).

Equivalent reformulation that the reference solution uses: subtract node.val before recursing, so the stack frame is (child, remaining - parent.val). Then a leaf is a hit when remaining == leaf.val. Both forms are correct; pick whichever you find clearer.

For 10⁴-node skewed inputs, use an iterative DFS with a stack of (node, remaining_after_subtracting_node) pairs. Initial frame: (root, target - root.val). On each pop, check leaf-and-zero; otherwise push children.

Worked example

Input:
[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]
target = 22

           5
          / \
         4   8
        /   / \
       11  13  4
      / \       \
     7   2       1

hits(5, 22):
  hits(4, 17):
    hits(11, 13):
      hits(7, 2):  leaf, 2 != 7 -> false
      hits(2, 2):  leaf, 2 == 2 -> true

Answer: true. The matching path is 5 -> 4 -> 11 -> 2.

Negative example:

Input:
[1, 2, 3]
target = 5

   1
  / \
 2   3

Root-to-leaf paths sum to 1+2 = 3 and 1+3 = 4. Neither hits 5.
Answer: false.

Complexity

  • Time: O(n). Worst case visits every node once.
  • Space: O(h) for the stack.

Common pitfalls

  • Treating an internal node as a leaf when its value equals remaining: the spec is root-to-leaf. An internal node whose value alone equals the target is not a hit unless it is a leaf (has no children). Many candidates lose this case.
  • Empty tree returning true when target is zero: there are no paths in the empty tree, so the answer is always false, including when target == 0. Some implementations naively return "no nodes consumed, target is zero, so true". Wrong.
  • Confusing "any path" with "root-to-leaf path": this problem requires the path to start at the root and end at a leaf. path-sum-iii (a variant) drops both constraints and is significantly harder.
  • Sign errors: values can be negative, so the running remaining can go negative and then back to zero. Do not prune on "remaining went negative"; continue the descent.

Where this shows up in the enterprise

  • AWS Route 53 with weighted routing: each path through the routing tree carries a cumulative weight; "does any path sum to the requested weight?" is a path-sum question.
  • CDN failover policies: Cloudflare and Fastly compute cumulative latency along a routing tree branch and pick branches that hit a target latency budget.
  • PostgreSQL query plans: cumulative cost along a plan-tree branch determines whether a candidate plan is admissible against a statement_timeout budget.
  • MongoDB aggregation: cumulative document size after each pipeline stage; pipelines that hit a memory threshold along any branch are rejected.
  • TypeScript compiler: cumulative depth into nested types along a type-resolution path; the compiler short-circuits when a budget is exceeded.
  • Babel and ESLint: cumulative complexity along AST paths drives the cyclomatic-complexity rule and similar metrics.
  • Game AI: chess engines and Go programs accumulate evaluation along a search path; a leaf is the final position, the path sum is the principal-variation evaluation.
  • Cloud cost allocation: cumulative cost along an org-tree branch decides which sub-departments hit their quarterly budget.

The pattern is universal: any time a tree has additive edge or node weights and somebody asks "is there a path of a particular total?", you are running path-sum.

Variants you'll see elsewhere

  • path-sum-ii: return all matching paths, not just yes/no.
  • path-sum-iii: any node-to-node path (not constrained to root or leaf); subarray-sum-equals-k on tree paths.
  • binary-tree-maximum-path-sum: maximum sum among all paths; the harder cousin.
  • sum-root-to-leaf-numbers: build a base-10 number along the path, sum across all leaves.
  • sum-of-distances-in-tree: aggregate distances rather than node values.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests and per-session dynamic private tests. The dynamic suite includes paths with negative values that briefly take the running sum negative before returning to the target, and trees where only an internal node (never a leaf) has value equal to the target.
  2. Hints are graduated. The first hint asks what to carry as you descend. The third gives you the full skeleton. Each hint costs integrity.
  3. The AI training assistant offers Explain, Review, Find Bugs, Add Comments, Optimise at small costs in exam mode; free in practice.
  4. The dispute flow runs after the verdict. The common mistake on this problem is the "empty tree with target zero returns true" bug; the reviewer can confirm the spec.

Read the concept, attempt in practice mode, take hints when stuck, then redo in exam mode. When you can write the carry-down DFS in under four minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write has_path_sum by hand. An agent will. Your job is to:

  1. Recognise that "is there a root-to-leaf path of total X" is a depth-first carry-down problem, and that the leaf check is the entire base case.
  2. Tell the agent precisely: "DFS carrying the remaining budget down, the success predicate fires only at leaves, the empty tree returns false unconditionally".
  3. Read the agent's code and verify (a) the leaf check (no children), (b) the empty-tree base case, (c) the iterative form for skewed input.
  4. Stress-test on the edge cases the agent will silently miss: the empty tree with target = 0, a single node with value equal to target, a path with negative values dipping below zero on the way to a match.

Candidates who can name "this is path-sum, carry the remaining budget down to a leaf" within five seconds are the ones who direct AI agents productively. Candidates who cannot recognise the pattern end up approving generated code that enumerates all paths into a list and only then checks sums, allocating memory it does not need. parikshan is built to train the first kind.