I’m pretty sure I got this as a test question in “CS 102”, my data structures and algorithms course. The depth (or the height) of a tree. I really like phrasing this as the height of the tree, to be honest. My solution, as you see below, involves “adding 1” to the children’s depth. Especially if this is used as a teaching exercise, focusing on height helps avoid unneeded difficulties.

When we go over it in review sessions I’ve found students are often confused by the definition of the problem itself. It invites off-by-one errors, and also depth-versus-height. Especially when we say “now add one to the depth” — well, why are we increasing the depth as we go up the tree? It may be clear after-the-fact, but that can even detract from the satisfaction of solving it. If you can get them past that (or cleverly avoid them having to consider that aspect at all) it’s a great exercise.

Oh, and in this particular problem description, the math-y definition invites a certain implementation (ah, trace paths through the tree, very explicitly!). I think that’s a valuable thing to consider, the idea that a mechanical definition may very well different substantively from the “real” implementation, but I would rather introduce that idea outside the context of an interview or academic question. More like lecture material.

class Solution(object):
    def maxDepth(self, root):
        if root is None:
            return 0
        leftDepth = self.maxDepth(root.left)
        rightDepth = self.maxDepth(root.right)
        maxChild = max(leftDepth, rightDepth)
        return maxChild + 1

More binary tree material can be found here.