Return Up or Pass Down
Recursion: lesson 6 of 8
Every recursion moves information one of two ways. Pick one.
Lesson 6 of 8 · 6 min
Return Up or Pass Down
Step 1 of 11
The same tree, asked two different questions. What travels — and which way — decides the shape of the code.
The Idea
Recursive functions differ in which direction information travels. Return up: children compute, the parent combines, the answer grows on the way back.
Pass down: the parent hands context to each child as an argument, and a base case reports a finished result. Choosing the wrong direction is why a recursion turns into a tangle of globals.
Real-World Example
Two ways to audit a company. Ask every department to total its own spend and report upwards, or walk in with the budget and hand each department what remains. Both work; mixing them halfway through does not.
The Code
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def deepest(n): # RETURN UP: the children answer, the parent combines
if not n: return 0
return 1 + max(deepest(n.left), deepest(n.right))
def paths(n, so_far=()): # PASS DOWN: the parent hands context to the children
if not n: return []
trail = (*so_far, n.val)
if not n.left and not n.right: return [trail]
return paths(n.left, trail) + paths(n.right, trail)
root = Node(1, Node(2, Node(4)), Node(3))
print(deepest(root)) # 3
print(paths(root)) # [(1, 2, 4), (1, 3)]Your turn
What does this print?
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def paths(n, so_far=()):
if not n: return []
trail = (*so_far, n.val)
if not n.left and not n.right: return [trail]
return paths(n.left, trail) + paths(n.right, trail)
print(paths(Node(1, Node(2, Node(4), Node(5)), Node(3)))[1])Mini quiz
1 / 3