Path Sum III

medium ~25 min

TreeNode(val, left=None, right=None) is in the starter. Keep it.

A downward path starts at any node and moves only from parent to child, stopping at any node on the way. It doesn't have to start at the root or end at a leaf, and a single node on its own is a path too. Write count_paths(root, target) -> int: how many downward paths have values adding up to target.

#            4
#          /   \
#         2     -1
#        / \      \
#       3  -2      5
#      /     \
#     1       6
count_paths(root, 6)   # 4: [4, 2], [2, 3, 1], [2, -2, 6] and [6]

The example tree with the nodes on paths adding up to 6 in green; the paths end at 2 (4, 2), at 1 (2, 3, 1) and at 6 (2, -2, 6, and 6 on its own)

count_paths(root, 4)                       # 5: [4], [4, 2, -2], [3, 1], [-2, 6] and [-1, 5]
count_paths(from_list([0, 0, None, 0]), 0) # 6: each of the 3 nodes, 2 pairs and the whole chain
count_paths(None, 0)                       # 0

Up to 150,000 nodes; values are between -10^4 and 10^4, target between -10^9 and 10^9.
Trees can be up to 3,000 levels deep. If you recurse, raise the limit first (sys.setrecursionlimit(10_000)), or use an explicit stack.
Checking every path that starts at each node passes the correctness tests.

⭐ Bonus: a speed test on a 128,000-node tree with 2,006 levels earns a star in O(n) time.

Show hint

Think of the running sum from the root down to the current node, prefix. A path that ends here and adds up to target starts right below an ancestor whose running sum was prefix - target. Keep a count of the running sums on the current root-to-node path in a dictionary, adding on the way down and removing on the way back up.

Topic: Binary trees. Recursive return values (height, best path), BFS by level, BST invariants.

Read the visual guide