422. Print All K-Sum Paths in a Binary Tree

Given a binary tree and a target sum k, find every downward path (a path does not need to start at the root or end at a leaf, but it must move strictly from a node to a descendant) whose node values sum to exactly k. Print each such path on its own line, values space-separated; if no such path exists, print 'None'. Consider every node as a possible starting point in preorder (root, then left subtree, then right subtree); for each starting point, extend the path downward exploring the left subtree before the right subtree, and print a path as soon as its running sum equals k - this fixes the order paths appear in. The tree's input is given first, then k on the next line.

Input: First line contains space-separated level-order tokens describing the tree ('N' marks an absent child). Second line contains the target sum k. Output: Print each qualifying downward path's values, space-separated, one path per line, in the specified traversal order, or print 'None' if no path sums to k.

1 <= number of nodes <= 10^3

The DFS must CONTINUE even after finding one matching path from a given start, since node values could include negatives elsewhere in a more general variant, or simply because a longer path further down might independently ALSO sum to k - never assume a single match closes off the search from that start.

Find every downward path in a binary tree (starting anywhere, ending anywhere below it, always moving strictly downward) whose values sum to exactly k. Brute force: Enumerate every possible pair of (start node, end node) where end is a descendant of start, and sum the path between them directly - this can cost O(n²) or worse for deep trees, since each path sum could take O(depth) to compute from scratch. Optimised: Running a DFS from EVERY node as a potential start, while maintaining a running sum incrementally as the DFS descends (rather than recomputing the sum from scratch for each candidate path), keeps each individual downward search efficient - the preorder-then-left-before-right visiting order also conveniently fixes the required output order with no extra sorting needed.

Extend the single-DFS approach by maintaining a running prefix sum from the root to the current node, plus a hashmap from 'prefix sum value seen along the current root-to-node path' to the list of depths where it occurred (entries are added on entering a node and removed on backtracking out, just like the path array). At the current node with prefix sum S, looking up (S - k) in the hashmap instantly gives every ancestor depth that starts a k-sum path ending here, in O(1) average per lookup instead of scanning the whole path. This is the same technique used for 'Path Sum III', and it cuts the average-case work from quadratic down to linear (output-proportional work aside), while still reconstructing and printing paths in the specified order using the stored depth indices. Time: O(n) average Space: O(n)

Visit every node as a potential path-start in preorder; for each start node, independently launch a fresh DFS downward (left subtree before right), building up a brand-new path array from that start and checking the running sum at every node visited, printing whenever it equals k. Each start node's exploration is entirely self-contained and redoes all the work of walking its subtree from scratch, which is correct but wastes effort since the subtree under a node gets walked repeatedly - once for that node's own start, and again nested inside every ancestor start's exploration. Time: O(n^2) worst case (skewed tree) Space: O(n^2) worst case (many independently stored paths)

Perform just one DFS over the whole tree (preorder: root, then left, then right), maintaining a single running array of values from the root down to the current node, appending the current value on entry and removing it on backtrack out (standard 'path + backtrack' technique). At each node, scan backward over the current path array checking whether any suffix sums to k (a node further up the path is a valid 'start'), and print the corresponding path segment when it does, in the required start-then-extend order. This avoids storing many separate path copies - there is only ever one reused buffer - so memory drops sharply, even though checking every suffix at every node keeps the worst-case time the same as brute force. Time: O(n^2) worst case Space: O(n)

1. Visit every node in PREORDER as a possible STARTING point for a path. 2. From each starting point, run a small DFS that extends the path downward (left before right), tracking a running sum and checking it against k at every step. 3. The moment the running sum equals k, record and print that path - but continue the DFS further, since a longer path starting at the same node might ALSO sum to k. 4. Because starting points are visited in preorder and each one's own search explores left before right, the overall output order is fully and uniquely determined.

Time: O(n²) in the worst case (a search from every one of the n nodes, each potentially examining O(n) descendants in a skewed tree), though much faster in practice on balanced trees. Space: O(h) for the recursion stack at any given time, plus space for the current path being tracked.

Test with no path summing to k (print 'None'), a single node whose own value equals k, a starting node with multiple valid downward paths beneath it, and a tree at the maximum size of 10^3 nodes for performance.

Be ready to clarify explicitly that a path doesn't need to start at the root or end at a leaf - just move strictly downward - this flexibility is what requires trying EVERY node as a potential starting point, not just the root.