Return one thing, update another

The most important idea in the unit. What a node reports to its parent is not always what the answer is.

Why it works

The two quantities, named

What a node returns is the best value of something that continues upward: a path going down one side only, since a parent can only extend a path through one of its children.

What a node updates is a running best that considers the case where this node is the topmost point of the answer, which may combine both children.

Write those two sentences before writing the function. Every problem of this shape is the same two sentences with different quantities in them.

Here are the mechanics on a deliberately boring pair of quantities, so that only the structure is on show. The depth travels upward as a return value. The count of nodes with two children never travels anywhere; it is recorded where it is found.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def deepest_and_forks(root):6    forks = 0                            # updated, never returned7 8    def depth(node):9        nonlocal forks10        if node is None:11            return 012        left = depth(node.left)13        right = depth(node.right)14        if node.left and node.right:15            forks += 1                   # recorded here, not passed upward16        return 1 + max(left, right)      # what the parent can extend17 18    return depth(root), forks19 20print(deepest_and_forks(T(1, T(2, T(4), T(5)), T(3))))21print(deepest_and_forks(T(1, T(2, T(3, T(4))))))

Trace it· 8 min

Trace the two quantities

Run deepest_and_forks on the tree T(1, T(2, T(4), T(5)), T(3)). For each node give what depth returns and what forks holds immediately after that node has been handled. Nodes are visited in postorder: 4, 5, 2, 3, 1.

node	returns	forks after
4
5
2
3
1

Problem· 22 min

Diameter Of 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 deepest_and_forks(root):6 forks = 0 # updated, never returned7 8 def depth(node):9 nonlocal forks10 if node is None:11 return 012 left = depth(node.left)13 right = depth(node.right)14 if node.left and node.right:15 forks += 1 # recorded here, not passed upward16 return 1 + max(left, right) # what the parent can extend17 18 return depth(root), forks19 20print(deepest_and_forks(T(1, T(2, T(4), T(5)), T(3))))21print(deepest_and_forks(T(1, T(2, T(3, T(4))))))

node

returns

forks after