A recursive depth-first traversal visits every node in a balanced binary tree with n node…

A recursive depth-first traversal visits every node in a balanced binary tree with n nodes. What are its usual time and call-depth bounds?

1. O(n) time and O(log n) call depth
2. O(log n) time and O(n) call depth
3. O(n log n) time and O(1) call depth
4. O(n) time and O(n) call depth for every tree shape