Combining what the children return

Measuring a tree, and walking two trees in step.

Key idea

Measuring downward

Some measurements are about how far the tree extends. The pattern is the same template, with a combination that takes the larger or smaller of the two children's answers and adds the current node.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def longest_run_down(node, value):6    """Longest downward path of nodes all holding this value."""7    if node is None or node.val != value:8        return 09    return 1 + max(longest_run_down(node.left, value),10                   longest_run_down(node.right, value))11 12tree = T(7, T(7, T(7)), T(3))13print(longest_run_down(tree, 7))

Key idea

Walking two trees at once

The second kind of combination takes two trees and recurses on both in step: left against left, right against right. The base cases multiply, and getting them right is the whole difficulty.

There are three: both empty, exactly one empty, and both present. The middle case is the one people forget, and it is what stops the recursion from raising on a missing child.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def same_shape(a, b):6    """Ignores values, compares structure only."""7    if a is None and b is None:8        return True9    if a is None or b is None:10        return False11    return same_shape(a.left, b.left) and same_shape(a.right, b.right)12 13print(same_shape(T(1, T(2)), T(9, T(8))))14print(same_shape(T(1, T(2)), T(1, None, T(2))))

What comes next

The two problems below are these two shapes exactly. One measures how deep the tree goes, the other compares two trees node by node.

Both are short. Get the base cases right and there is nothing else to them, which is why they arrive here rather than later.

Quick check· 5 min

How many base cases?

You are writing a function that compares two trees for equality of both structure and values. How many base cases does it need before the recursive step?

Two: both empty returns True, exactly one empty returns FalseOne: if either is empty, return whether both are emptyThree: both empty, left empty, right empty, each returning separatelyNone; the recursion handles empty children naturally

Problem· 12 min

Maximum Depth 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.

Problem· 14 min

Same 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 same_shape(a, b):6 """Ignores values, compares structure only."""7 if a is None and b is None:8 return True9 if a is None or b is None:10 return False11 return same_shape(a.left, b.left) and same_shape(a.right, b.right)12 13print(same_shape(T(1, T(2)), T(9, T(8))))14print(same_shape(T(1, T(2)), T(1, None, T(2))))