Recursion and Trees
Carrying information down the tree
Not every recursion sends answers upward. Some send context downward as a parameter.
Key idea
The other direction
Everything so far had children reporting upward. The opposite is a recursion where a node needs to know something about the path taken to reach it: its depth, the running sum above it, the largest value seen on the way down.
A node cannot look up at its ancestors, so that information has to arrive as a parameter. Each call passes the updated context down to its children.
Why it works
Some problems need both directions
Context flows down as a parameter and results flow up as a return value, and a single function can do both at once. That is the general shape and it covers most of what remains in this unit.
Name the two explicitly when you plan: what does a node need to know from above, and what does it owe its parent? Answering both questions before writing the signature makes the signature obvious.
Gotcha
Be careful with default parameter values
Using a mutable default such as def walk(node, seen=[]) is a well-known Python trap: the same list is shared across every call to the function, so a second call sees leftovers from the first.
Defaults that are numbers, strings, or None are safe because they cannot be mutated. When you need a mutable default, use None and create the real value inside the function.
Tip
Update the context before descending, not after
The value passed to the children must already include the current node, since the children's ancestors include it. Passing the unmodified context down is a one-word error that makes every node compare against its grandparent instead of its parent.
The check for this is the two-level tree: a root and one child. If the child is compared against nothing rather than against the root, the context update is in the wrong place.
Predict the output: a list as a default parameter
The context being carried down is a list, given an empty list as its default. Two independent trees are walked, one after the other. Type both lines it prints.
Count Good Nodes In Binary Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.