Date: 2026-06-06
Time: 18:31
path-sum/solution.pyThis file implements LeetCode 112 - Path Sum, a classic binary tree problem. It determines whether any root-to-leaf path in a binary tree has node values that sum to a given target. The file is self-contained: it defines the tree data structure, the solution function, and a comprehensive test suite.
TreeNode — Standard binary tree node with val, left, and right. This is the local definition used by both the solution and tests; it mirrors LeetCode's provided class.
hasPathSum(root, targetSum) -> bool — The core algorithm. Contract:
True iff there exists a path from root to a leaf (both children None) where the sum of all node values equals targetSum.False for an empty tree (root is None), even if targetSum is 0.TestPathSum — Nine test cases covering the key boundaries: standard trees, empty tree, single node, negative values, left-only paths, zero target, and the critical edge case where the sum matches at a non-leaf node (which must return False).
Recursive subtraction — Rather than accumulating a running sum downward, the function subtracts the current node's value from targetSum and passes the remainder to children. At a leaf, it checks root.val == targetSum (i.e., the remainder equals the leaf's value). This avoids threading an accumulator parameter.
Base-case-first recursion — The function handles three cases in order: (1) null node → False, (2) leaf node → equality check, (3) internal node → recurse on children with short-circuit or. This ordering ensures the null check acts as both the "empty tree" case and the guard for recursive calls on absent children.
Imports: Only stdlib — annotations (for deferred type evaluation of the self-referential TreeNode), unittest, and typing.Optional.
Imported by: path-sum/testsolution.py and hundreds of other test files across the repo. The "Imported By" list in the prompt is misleading — those other test files don't actually import from this file. They appear because the repo's dependency scanner likely flagged all test files sharing the same TreeNode pattern. The real consumer is path-sum/testsolution.py.
hasPathSum(root, 22)
root=5, not None, not leaf → remainder = 22-5 = 17
hasPathSum(left=4, 17)
not None, not leaf → remainder = 17-4 = 13
hasPathSum(left=11, 13)
not None, not leaf → remainder = 13-11 = 2
hasPathSum(left=7, 2) → leaf, 7≠2 → False
hasPathSum(right=2, 2) → leaf, 2==2 → True ← short-circuits
→ True
→ True (short-circuits, never checks right=None)
→ True
→ True (short-circuits, never checks right=8 subtree)
The or short-circuits: once a valid path is found in the left subtree, the right subtree is never explored.
1. Leaf-only matching — A path must terminate at a leaf. Internal nodes whose cumulative sum equals the target are explicitly rejected. testnonleafsummatch validates this: a tree 1→2→3 with target 1 returns False because node 1 is not a leaf.
2. Null tree is always False — Even hasPathSum(None, 0) returns False. An empty tree has no paths, therefore no path can match any target.
3. No mutation — The tree and target are never modified. The remainder is a new local variable each frame.
None. The function assumes valid inputs (a well-formed tree or None, and an integer target). No exceptions are raised or caught. This is appropriate for a LeetCode solution where inputs are guaranteed by the problem constraints.