小编ds2*_*s25的帖子

我正在研究时间和空间的复杂性.我以递归和迭代方式解决二叉树问题.递归使用底层堆栈,因此:

如果我想在BST中找到最小元素,那么如果我使用递归,那么我的空间复杂度就是

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

但如果我使用迭代解决这个问题,那么空间复杂度是多少？迭代方法的空间复杂度与递归方法相同如何？我在这里没有使用任何辅助空间,我只是使用1 while循环.我在这里很困惑.

迭代方法

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);
}