How do we use a binary tree?

Almost every binary tree solution has the same shape. Once you see it, most tree problems become a matter of filling in two blanks: what does an empty tree return, and how do I combine my children's answers with my own value.

The recursive template

solve(node):
    if node is null:   return the answer for an empty tree     <- base case
    left  = solve(node.left)                                   <- trust it
    right = solve(node.right)                                  <- trust it
    return combine(node.val, left, right)

The hard part is the middle two lines: you have to trust that the recursive calls return the right answer for the subtrees, without tracing them in your head. That isn't magic — it's induction. If solve is right for smaller trees (and it's right for the empty tree), then combining their answers correctly makes it right for this tree too.