A recursion that calls another recursion

One walk to visit every node, another to test each one. Two functions, and the cost multiplies.

Key idea

Separate the walking from the testing

Some questions are of the form: does any node in this tree satisfy some property that is itself about a whole subtree?

Trying to do both jobs in one function produces something confusing. Write two: an outer one that visits every node, and an inner one that answers the property for a single node. The outer one calls the inner one at each stop.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def is_perfect_pair(node):6    """Does this node have two children holding equal values?"""7    return (node is not None8            and node.left is not None9            and node.right is not None10            and node.left.val == node.right.val)11 12def count_perfect_pairs(node):13    if node is None:14        return 015    here = 1 if is_perfect_pair(node) else 016    return here + count_perfect_pairs(node.left) + count_perfect_pairs(node.right)17 18tree = T(1, T(2, T(5), T(5)), T(3, T(7), T(7)))19print(count_perfect_pairs(tree))

Tip

Stopping early

When the question is does any rather than how many, the outer walk can stop at the first success. Python's or short-circuits, so writing the recursive calls joined by or gives that for free.

The order of the checks then matters for speed but not for correctness: testing the current node before recursing means an early match costs nothing.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def any_perfect_pair(node):6    if node is None:7        return False8    if (node.left and node.right and node.left.val == node.right.val):9        return True10    return any_perfect_pair(node.left) or any_perfect_pair(node.right)11 12print(any_perfect_pair(T(1, T(2, T(5), T(5)))))13print(any_perfect_pair(T(1, T(2))))

Predict the output· 5 min

Predict the output: matching from the wrong place

same_shape checks two trees for an exact match. The pattern here does appear inside the big tree, but not starting at the node being tested. Type the two values it prints, separated by a single space.

Python

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    if a is None and b is None:7        return True8    if a is None or b is None:9        return False10    return (a.val == b.val11            and same_shape(a.left, b.left)12            and same_shape(a.right, b.right))13 14big = T(3, T(4, T(1), T(2)), T(5))15pattern = T(4, T(1), T(2))16 17print(same_shape(big, pattern), same_shape(big.left, pattern))

Printed output

Problem· 20 min

Subtree Of Another 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 is_perfect_pair(node):6 """Does this node have two children holding equal values?"""7 return (node is not None8 and node.left is not None9 and node.right is not None10 and node.left.val == node.right.val)11 12def count_perfect_pairs(node):13 if node is None:14 return 015 here = 1 if is_perfect_pair(node) else 016 return here + count_perfect_pairs(node.left) + count_perfect_pairs(node.right)17 18tree = T(1, T(2, T(5), T(5)), T(3, T(7), T(7)))19print(count_perfect_pairs(tree))

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def any_perfect_pair(node):6 if node is None:7 return False8 if (node.left and node.right and node.left.val == node.right.val):9 return True10 return any_perfect_pair(node.left) or any_perfect_pair(node.right)11 12print(any_perfect_pair(T(1, T(2, T(5), T(5)))))13print(any_perfect_pair(T(1, T(2))))

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 if a is None and b is None:7 return True8 if a is None or b is None:9 return False10 return (a.val == b.val11 and same_shape(a.left, b.left)12 and same_shape(a.right, b.right))13 14big = T(3, T(4, T(1), T(2)), T(5))15pattern = T(4, T(1), T(2))16 17print(same_shape(big, pattern), same_shape(big.left, pattern))