Recursion and Trees
The tree recursion template
The structure is already recursive, so the code mirrors it. Almost every tree function is the same four lines.
Key idea
What a binary tree node is
A node holds a value and references to a left and a right child, either of which may be None. None is how the structure ends, and it is also the base case of almost every function you will write here.
The key fact: a child is itself a complete tree. That is why the leap of faith works so cleanly on trees. When you call your function on node.left, you are calling it on a smaller tree of exactly the same kind.
Why it works
The template
Handle None. Recurse on both children. Combine their answers with the current node. That is the entire structure of most tree functions, and the only thing that changes between problems is the combination step.
Gotcha
The base case returns the identity
For a sum the empty tree is 0. For a count it is 0. For a product it would be 1, for a maximum it would be negative infinity, and for a boolean like are all values positive it would be True.
The rule: the base case returns whatever value makes the combination step behave as if that branch were not there. Getting it wrong usually produces answers that are off by a constant per missing child, which is confusing to debug and instant to fix once you check this.
Key idea
Returning a tree rather than a value
Some problems transform the tree instead of measuring it. The template is unchanged; the combination step rewires children and the function returns a node.
The same discipline from the linked list unit applies: if a step overwrites something you still need, save it first.
Cost
The cost of a full traversal
Every one of these visits each node once and does constant work there, so they are O(n) time.
Space is the recursion depth, which is the height of the tree. That is O(log n) for a balanced tree and O(n) for a degenerate one shaped like a linked list. Quote the height, and say what it becomes in the worst case, since that is the follow-up.
Template drills
Four questions, one shape. max_value returns the largest value, or None for an empty tree. count_leaves counts nodes with no children. all_positive reports whether every value is positive. mirror swaps every node's children in place and returns the root.
Tests
tree = T(1, T(2, T(4), T(5)), T(3)) print(max_value(tree), max_value(None)) print(count_leaves(tree), count_leaves(None), count_leaves(T(9))) print(all_positive(tree), all_positive(T(1, T(-2))), all_positive(None)) print(to_list(mirror(T(1, T(2), T(3)))))
Output
Run the tests when you are ready.
Invert 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.