Path Sum Variants
Trees & BST: lesson 11 of 14
Same tree, three questions — and three different things to carry.
Lesson 11 of 14 · 6 min
Path Sum Variants
Step 1 of 7
Does any root-to-leaf path add up to 20? Carry the remainder down instead of a running total.
The Idea
"Does a root-to-leaf path add up to the target?" is answered by carrying the remainder down: subtract each node, and a leaf only has to hit zero.
"How many paths anywhere add up to it?" needs more: at each node, keep the running sum of every path an ancestor started, plus one starting here.
Real-World Example
A delivery route budget. The first question is whether one full route from depot to doorstep costs exactly the allowance. The second asks how many stretches of road anywhere in the network cost that much.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def has_path(n, target): # root to leaf: carry the remainder down
if not n: return False
rest = target - n.val
if not n.left and not n.right: return rest == 0
return has_path(n.left, rest) or has_path(n.right, rest)
def count_paths(n, target, open_sums=()): # any node down to any node
if not n: return 0
sums = [s + n.val for s in open_sums] + [n.val] # grow every open path, open one more
return (sums.count(target)
+ count_paths(n.left, target, sums)
+ count_paths(n.right, target, sums))
root = Node(5, Node(4, Node(11)), Node(8, Node(3)))
print(has_path(root, 20), count_paths(root, 11)) # True 2Your turn
Put the steps in the right order.
- At a leaf, report a hit when the remainder is exactly zero
- Subtract the node's value from the target that arrived
- Start at the root with the full target
- Otherwise hand the new remainder to both children and take either answer
Mini quiz
1 / 3