ArrayList containing references to TreeNodes, what is the space complexity?

Question

   TreeNode root = new TreeNode(5);
    ArrayList<TreeNode> arr = new ArrayList<TreeNode>();
    for(int i = 0; i < n; i++){
        arr.add(root);
    }

In the above code, a single TreeNode object is added into the ArrayList<TreeNode> arr for n times. I think that arr should have a space complexity of O(1) because it is saving references to single memory block on heap. I am discussing this with my friends and they have different opinion that it might have O(n) complexity. What do you guys think?

Answer 1

You're saving references, but they are still n references. I think you're actually looking for a memory overhead for storing n objects in an ArrayList. The memory used will probably be dominated by the actual objects, but there is still an array with length n backing that ArrayList holding the references.