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.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5tree = T(1, T(2, T(4)), T(3))6print(tree.val, tree.left.val, tree.left.left.val, tree.right.val)7print(tree.right.left)

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.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def total(node):6    if node is None:7        return 0                       # base case8    left = total(node.left)            # trust it9    right = total(node.right)          # trust it10    return node.val + left + right     # combine11 12def count_nodes(node):13    if node is None:14        return 015    return 1 + count_nodes(node.left) + count_nodes(node.right)16 17tree = T(1, T(2, T(4)), T(3))18print(total(tree), count_nodes(tree))

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.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def to_list(node):6    if node is None:7        return None8    return [node.val, to_list(node.left), to_list(node.right)]9 10def increment_all(node):11    if node is None:12        return None13    node.val += 114    increment_all(node.left)15    increment_all(node.right)16    return node17 18tree = T(1, T(2), T(3))19print(to_list(increment_all(tree)))

Code lab· 25 min

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.

solution.py

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 tests to see output.

Problem· 15 min

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.

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def total(node):6 if node is None:7 return 0 # base case8 left = total(node.left) # trust it9 right = total(node.right) # trust it10 return node.val + left + right # combine11 12def count_nodes(node):13 if node is None:14 return 015 return 1 + count_nodes(node.left) + count_nodes(node.right)16 17tree = T(1, T(2, T(4)), T(3))18print(total(tree), count_nodes(tree))

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def to_list(node):6 if node is None:7 return None8 return [node.val, to_list(node.left), to_list(node.right)]9 10def increment_all(node):11 if node is None:12 return None13 node.val += 114 increment_all(node.left)15 increment_all(node.right)16 return node17 18tree = T(1, T(2), T(3))19print(to_list(increment_all(tree)))

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)))))