Estimate the running time of counting nodes in a binary tree
Hint 1. You say the running time is $O(2^N)$ but what is $N$?  $2^N$ would indeed be bad if $N$ were the number of nodes.

Hint 2. How many times does your code visit each node in the tree?  How much time does it spend on each node?