Carrying information down

In some questions a node cannot decide by looking at its children alone; it needs information from above. Does some root-to-leaf path add up to the target? You hand each node "what is left by here" as a parameter; if at a leaf what is left is exactly the leaf's value, the path is found.

1def has_path(node, left):
2    if node is None:
3        return False
4    if node.left is None and node.right is None:
5        return left == node.val
6    rest = left - node.val
7    return has_path(node.left, rest) or has_path(node.right, rest)

Because the path has to end at a leaf, the decision is made at the leaf, not at an empty node. or stops at the first path found; if the left side returns True the right is never looked at.

Checking a search tree works on the same idea: you hand each node the range its value must stay inside. Going left the upper bound becomes the node's value, going right the lower bound does. That way a node is compared not only with its parent but with every ancestor above it.

Tasks