平衡二叉搜索树递归算法空间复杂度疑问：为何选C而非O(logN)？

题目背景 #

在含N个节点的平衡二叉搜索树上实现某递归算法，该算法需先递归左子树再递归右子树（类似中序遍历），题目询问其空间复杂度的正确描述。给出的选项包括：

• A：恰好O(logN)
• C：至少O(logN)，但可能更糟

我原本以为调用栈的空间复杂度应该是恰好O(logN)，疑惑为什么正确答案是C？

解答 #

• 平衡二叉树的高度严格为O(logN)，所以递归调用栈的深度固定是O(logN)，这部分是算法空间开销的下限，也就是必然存在的O(logN)空间消耗。
• 但题目问的是整个算法的空间复杂度，而非仅递归调用栈的空间。如果这个递归算法在执行过程中需要额外存储数据（比如将遍历到的节点值存入数组、缓存递归过程中的中间计算结果等），这部分额外空间的开销可能达到O(N)，导致整体空间复杂度超过O(logN)。
• 选项A的“恰好O(logN)”意味着空间复杂度不可能更高，但实际上算法的额外操作完全可能带来更大的空间开销；而选项C准确描述了这种情况：调用栈的O(logN)是必须的下限，算法的额外逻辑可能让空间复杂度变得更糟。

内容的提问来源于stack exchange，提问作者YumekaMengjiaLYU