LeetCode 173: Binary Search Tree Iterator (Inorder Stack Iterator)
LeetCode 173Binary TreeDesignStackToday we solve LeetCode 173 - Binary Search Tree Iterator. The key is to simulate inorder traversal lazily, so each call to next() is efficient and stateful.
Source: https://leetcode.com/problems/binary-search-tree-iterator/
English
Problem Summary
Implement a BST iterator with methods next() and hasNext(). It should return the next smallest number each time.
Key Insight
BST inorder traversal is naturally sorted. Instead of traversing all nodes up front, keep a stack of the current left spine. This is a lazy iterator: we only process what we need.
Optimal Algorithm (Lazy Inorder with Stack)
1) Constructor: push the root and all its left descendants onto stack.
2) hasNext(): stack non-empty means next element exists.
3) next(): pop top node (current smallest).
4) If popped node has right child, push that right child and all its left descendants.
5) Return popped value.
Complexity Analysis
Time: O(1) amortized per next(), because each node is pushed/popped once.
Space: O(h), where h is tree height.
Common Pitfalls
- Precomputing full inorder array violates intended memory usage.
- Forgetting to push the left chain of the right subtree after next().
- Misunderstanding amortized O(1) and assuming each next() is worst-case O(h) only.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class BSTIterator {
private Deque<TreeNode> stack = new ArrayDeque<>();
public BSTIterator(TreeNode root) {
pushLeft(root);
}
private void pushLeft(TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
public int next() {
TreeNode cur = stack.pop();
if (cur.right != null) pushLeft(cur.right);
return cur.val;
}
public boolean hasNext() {
return !stack.isEmpty();
}
}type BSTIterator struct {
st []*TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
it := BSTIterator{}
it.pushLeft(root)
return it
}
func (it *BSTIterator) pushLeft(node *TreeNode) {
for node != nil {
it.st = append(it.st, node)
node = node.Left
}
}
func (it *BSTIterator) Next() int {
n := len(it.st)
cur := it.st[n-1]
it.st = it.st[:n-1]
if cur.Right != nil {
it.pushLeft(cur.Right)
}
return cur.Val
}
func (it *BSTIterator) HasNext() bool {
return len(it.st) > 0
}class BSTIterator {
stack<TreeNode*> st;
void pushLeft(TreeNode* node) {
while (node) {
st.push(node);
node = node->left;
}
}
public:
BSTIterator(TreeNode* root) {
pushLeft(root);
}
int next() {
TreeNode* cur = st.top();
st.pop();
if (cur->right) pushLeft(cur->right);
return cur->val;
}
bool hasNext() {
return !st.empty();
}
};class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.st = []
self._push_left(root)
def _push_left(self, node: Optional[TreeNode]) -> None:
while node:
self.st.append(node)
node = node.left
def next(self) -> int:
cur = self.st.pop()
if cur.right:
self._push_left(cur.right)
return cur.val
def hasNext(self) -> bool:
return len(self.st) > 0var BSTIterator = function(root) {
this.st = [];
this.pushLeft = function(node) {
while (node) {
this.st.push(node);
node = node.left;
}
};
this.pushLeft(root);
};
BSTIterator.prototype.next = function() {
const cur = this.st.pop();
if (cur.right) this.pushLeft(cur.right);
return cur.val;
};
BSTIterator.prototype.hasNext = function() {
return this.st.length > 0;
};中文
题目概述
实现一个二叉搜索树迭代器，支持 next() 和 hasNext()，并按从小到大的顺序返回节点值。
核心思路
BST 的中序遍历天然有序。我们不一次性展开整棵树，而是用栈维护“当前左链”，按需懒加载下一个最小值。
最优算法（栈维护中序惰性迭代）
1）初始化时，把根节点及其所有左孩子压栈。
2）hasNext() 判断栈是否为空。
3）next() 弹出栈顶（当前最小值）。
4）若该节点有右子树，则将右子树的整条左链压栈。
5）返回该节点值。
复杂度分析
时间复杂度：next() 均摊 O(1)，每个节点最多入栈和出栈一次。
空间复杂度：O(h)，h 为树高。
常见陷阱
- 把整棵树先中序存数组，空间不符合迭代器设计初衷。
- next() 后忘记处理右子树左链，导致顺序错误。
- 误把均摊复杂度理解为每次都严格 O(1)。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class BSTIterator {
private Deque<TreeNode> stack = new ArrayDeque<>();
public BSTIterator(TreeNode root) {
pushLeft(root);
}
private void pushLeft(TreeNode node) {
while (node != null) {
stack.push(node);
node = node.left;
}
}
public int next() {
TreeNode cur = stack.pop();
if (cur.right != null) pushLeft(cur.right);
return cur.val;
}
public boolean hasNext() {
return !stack.isEmpty();
}
}type BSTIterator struct {
st []*TreeNode
}
func Constructor(root *TreeNode) BSTIterator {
it := BSTIterator{}
it.pushLeft(root)
return it
}
func (it *BSTIterator) pushLeft(node *TreeNode) {
for node != nil {
it.st = append(it.st, node)
node = node.Left
}
}
func (it *BSTIterator) Next() int {
n := len(it.st)
cur := it.st[n-1]
it.st = it.st[:n-1]
if cur.Right != nil {
it.pushLeft(cur.Right)
}
return cur.Val
}
func (it *BSTIterator) HasNext() bool {
return len(it.st) > 0
}class BSTIterator {
stack<TreeNode*> st;
void pushLeft(TreeNode* node) {
while (node) {
st.push(node);
node = node->left;
}
}
public:
BSTIterator(TreeNode* root) {
pushLeft(root);
}
int next() {
TreeNode* cur = st.top();
st.pop();
if (cur->right) pushLeft(cur->right);
return cur->val;
}
bool hasNext() {
return !st.empty();
}
};class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.st = []
self._push_left(root)
def _push_left(self, node: Optional[TreeNode]) -> None:
while node:
self.st.append(node)
node = node.left
def next(self) -> int:
cur = self.st.pop()
if cur.right:
self._push_left(cur.right)
return cur.val
def hasNext(self) -> bool:
return len(self.st) > 0var BSTIterator = function(root) {
this.st = [];
this.pushLeft = function(node) {
while (node) {
this.st.push(node);
node = node.left;
}
};
this.pushLeft(root);
};
BSTIterator.prototype.next = function() {
const cur = this.st.pop();
if (cur.right) this.pushLeft(cur.right);
return cur.val;
};
BSTIterator.prototype.hasNext = function() {
return this.st.length > 0;
};
Comments