Quiz: Tree Inversion

To invert a binary tree, you swap every node's left and right children. What is the time complexity of the recursive approach?

1. A.$O(n)$ time, $O(h)$ space, where $h$ is the tree height
2. B.$O(n \log n)$ time, $O(n)$ space
3. C.$O(n^2)$ time, $O(1)$ space
4. D.$O(n)$ time, $O(n)$ space always