Space complexity of iterative vs recursive - Binary Search Tree

Question

I'm studying time & space complexity. I was solving binary tree problems recursively & iteratively. Recursion uses underlying stack and hence eg:

If I want to find the minimum element in BST then if I use recursion then my space complexity would be

Worst case : O(n) if tree is left skewed OR
best case: O(1) 
average case: O(h) height of left subtree

but if I solve this problem using iteration, what is the space complexity? How is the space complexity for an iterative approach same as recursive approach ? I'm not using any auxillary space in here, I'm just using 1 while loop. I'm confused here.

Iterative approach

int minValue(struct node* node) {
  struct node* current = node;

  /* loop down to find the leftmost leaf */
  while (current->left != NULL) {
    current = current->left;
  }
  return(current->data);
}

Answer 1

If you use a recursive approach, then at each stage, you have to make a recursive call. That means leaving the current invocation on the stack, and calling a new one. When you're k levels deep, you've got k lots of stack frame, so the space complexity ends up being proportional to the depth you have to search.

With your iterative code, you're allocating one variable (O(1) space) plus a single stack frame for the call (O(1) space). Your while loop doesn't ever allocate anything extra, either by creating new variables or object instances, or by making more recursive calls. So the only space you need, for your whole call, is the O(1) space taken up by the variable you create and the rest of the stack frame.

Whenever you can rewrite a recursive algorithm as a simple iteration, it's worth doing precisely because of this reduced space requirement.