Space Complexity - Java object array using exisiting objects

Question

Assuming I'm using Java, let's say I'm trying to determine whether a given binary tree is a BST.

I choose to approach solving the problem by creating an empty array (holds node objects), doing an inorder traversal of the tree (adding nodes into the array along the way), and then say 'True' if the array is one that is completely sorted afterwards.

Is the space complexity of this approach O(1) or O(n)?

When I create this new array to hold node objects that I come across in the tree while doing the traversal, am I putting in the actual objects (which I would be O(1) then since I'm not initializing any new objects?)

or are like copies of the nodes of the trees being stored into the array? (Thus, O(n) space.)

Feel free to correct me on any wrong assumptions I'm making.

Answer 1

If you are using an additional array of size n then your space requirements are at least O(n) irrespective whether you store just references or copies of the objects to the new array.

Also, if you use recursion for the traversal then you are using O(log n) for the stack.

Answer 2

This approach is O(n) regardless of whether you're copying entire objects or just pointers to them, because you made an array of size n to copy into. As it happens, though, you are copying only pointers (really the only option in Java), so you won't be duplicating the space consumed by nodes themselves.