Pre order traversal of an array
I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child.

By induction you can prove that the resulting tree is balanced since you are building trees of the same size at each side (+/- 1 node). Also is easy to prove that the result is a binary search tree, by construction.

With respect to the complexity, every node in the recursive execution tree takes constant time. Since you have a number of nodes proportional to the number of elements in your input, then the algorithm is O(n).