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.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def deeper_than(node, limit, depth=0):6    """Count nodes deeper than the given depth. The root is depth 0."""7    if node is None:8        return 09    here = 1 if depth > limit else 010    return (here11            + deeper_than(node.left, limit, depth + 1)12            + deeper_than(node.right, limit, depth + 1))13 14tree = T(1, T(2, T(4)), T(3))15print(deeper_than(tree, 0), deeper_than(tree, 1))

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.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def max_on_path(node, best_so_far=None):6    """Count nodes that are at least as large as everything above them."""7    if node is None:8        return 09    qualifies = best_so_far is None or node.val >= best_so_far10    updated = node.val if best_so_far is None else max(best_so_far, node.val)11    return ((1 if qualifies else 0)12            + max_on_path(node.left, updated)13            + max_on_path(node.right, updated))14 15print(max_on_path(T(3, T(1, T(3)), T(4, T(1), T(5)))))

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.

1def collect(value, into=[]):        # shared across calls2    into.append(value)3    return into4 5print(collect(1))6print(collect(2))                    # the 1 is still there7 8def safe(value, into=None):9    if into is None:10        into = []11    into.append(value)12    return into13 14print(safe(1), safe(2))

Predict the output· 5 min

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.

Python

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def values_down(node, seen=[]):6    if node is None:7        return seen8    seen.append(node.val)9    values_down(node.left, seen)10    values_down(node.right, seen)11    return seen12 13print(values_down(T(1, T(2))))14print(values_down(T(9)))

Printed output

Problem· 20 min

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.

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def deeper_than(node, limit, depth=0):6 """Count nodes deeper than the given depth. The root is depth 0."""7 if node is None:8 return 09 here = 1 if depth > limit else 010 return (here11 + deeper_than(node.left, limit, depth + 1)12 + deeper_than(node.right, limit, depth + 1))13 14tree = T(1, T(2, T(4)), T(3))15print(deeper_than(tree, 0), deeper_than(tree, 1))

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def max_on_path(node, best_so_far=None):6 """Count nodes that are at least as large as everything above them."""7 if node is None:8 return 09 qualifies = best_so_far is None or node.val >= best_so_far10 updated = node.val if best_so_far is None else max(best_so_far, node.val)11 return ((1 if qualifies else 0)12 + max_on_path(node.left, updated)13 + max_on_path(node.right, updated))14 15print(max_on_path(T(3, T(1, T(3)), T(4, T(1), T(5)))))

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def values_down(node, seen=[]):6 if node is None:7 return seen8 seen.append(node.val)9 values_down(node.left, seen)10 values_down(node.right, seen)11 return seen12 13print(values_down(T(1, T(2))))14print(values_down(T(9)))