There are N elements in the array. The recursive approach creates N nodes for the tree.
Space N nodes for N elements - O(N)
Time N calls for N nodes - O(N)
Although the recursion branches out to left and right by the power of 2, at the end of computation, N nodes have to be made, thus N calls to the recursive method.
It's O(n) both in run time and space
For run time, just consider how many times a particular number will be treated as a root->only once. So each number leads to a recursive call.
For space, just follow up the run time, each number leads to a recursive call, each recursive call takes O(1) space, n recursive calls takes O(n) space.