Trees

Trees are a Google staple, and almost every tree question is recursion in disguise. The hard part isn't the recursion itself, it's deciding what each node needs: an answer assembled from its children, or context handed down from its ancestors. Get that right and the code is short.

That one decision splits nearly all tree problems into two shapes. In the first, you solve the subtrees first and combine their results on the way back up. In the second, you carry information down as you descend and act on it at each node. Name which one you're in, and most tree interviews come unstuck.