Now this I’m certain is a classic. I like how it’s not, well, a single tree! A neat second-lecture problem on binary trees, I’d think.

class Solution(object):
    def isSameTree(self, p, q):
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False
        if not self.isSameTree(p.left, q.left):
            return False
        if not self.isSameTree(p.right, q.right):
            return False
        return True

This “design” or style of programming is curious. Would the students suspect that “I thought about enough cases, and figured if there’s no other reason, we can return true”? I guess reasoning by cases never felt very persuasive to me when I was starting out, it’s hard to convey that we really have covered all the cases. I don’t know what threshold I crossed to feel more confident about reasoning-by-cases. Now that I do feel comfortable, I think this can be a valuable real-world tool, too.

Other binary tree problems with solutions can be found here.

Postscript: About 9 months after posting this, I was adding more questions, and I had misread my notes and thought this wasn’t a question I solved yet. My new approach is almost character-for-character the exact as listed above! Surprising.