Binary Search Tree Iterator
Binary Search Tree Iterator is a medium trees & bst problem solved with the bst basics pattern.
The best approach, optimal (controlled stack of the left spine), runs in O(1) amortized per call time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flatten in-order into a list) up.
Problem
Design a class BSTIterator that walks a binary search tree in ascending order, one value at a time.
BSTIterator(TreeNode root)sets up the iterator for the tree rooted atroot. Conceptually, it starts just before the smallest value.int next()moves to the next value in ascending order and returns it.boolean hasNext()returnstrueif at least one value has not been returned yet.
next is only called when a value remains. The values returned by repeated next calls are exactly the in-order traversal of the tree.
Examples
Example 1
- Input
BSTIterator([6,2,9,null,4]), next(), next(), hasNext(), next(), next(), hasNext()- Output
2, 4, true, 6, 9, false- Why
- The in-order sequence of the tree is 2, 4, 6, 9; after four calls to next it is used up.
Example 2
- Input
BSTIterator([3]), hasNext(), next(), hasNext()- Output
true, 3, false- Why
- A single-node tree yields one value.
Constraints
- The tree has between
1and10^5nodes, and it is a valid binary search tree. 0 <= Node.val <= 10^6- At most
10^5calls are made in total, andnextis only called when a value remains. - Aim for
nextandhasNextin O(1) amortized time with O(h) extra memory (h = tree height).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (flatten in-order into a list) | O(n) constructor, O(1) per call | O(n) |
| Optimal (controlled stack of the left spine) | O(1) amortized per call | O(h) |
1Brute force (flatten in-order into a list)
O(n) constructor, O(1) per callThe full traversal happens up front; each call is then an index lookup.O(n)Every value of the tree is copied into the list.In the constructor, run an in-order traversal and store every value in a list. Keep an index into it: next returns the value at the index and advances it, and hasNext checks whether the index is still inside the list.
- Constructor: inorder(root) appends values to a list; idx = 0.
- next(): return values[idx++].
- hasNext(): return idx < values.size().
class BSTIterator {
private final List<Integer> values = new ArrayList<>();
private int idx = 0;
public BSTIterator(TreeNode root) {
inorder(root);
}
private void inorder(TreeNode node) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = node;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
values.add(cur.val);
cur = cur.right;
}
}
public int next() {
return values.get(idx++);
}
public boolean hasNext() {
return idx < values.size();
}
}class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.values = []
self.idx = 0
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
self.values.append(cur.val)
cur = cur.right
def next(self) -> int:
val = self.values[self.idx]
self.idx += 1
return val
def hasNext(self) -> bool:
return self.idx < len(self.values)class BSTIterator {
vector<int> values;
size_t idx = 0;
public:
BSTIterator(TreeNode* root) {
vector<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) {
st.push_back(cur);
cur = cur->left;
}
cur = st.back();
st.pop_back();
values.push_back(cur->val);
cur = cur->right;
}
}
int next() { return values[idx++]; }
bool hasNext() { return idx < values.size(); }
};class BSTIterator {
constructor(root) {
this.values = [];
this.idx = 0;
const stack = [];
let cur = root;
while (cur || stack.length) {
while (cur) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
this.values.push(cur.val);
cur = cur.right;
}
}
next() {
return this.values[this.idx++];
}
hasNext() {
return this.idx < this.values.length;
}
}2Optimal (controlled stack of the left spine)
O(1) amortized per callEvery node is pushed and popped exactly once over all n calls to next, so the total work is O(n).O(h)The stack holds at most one root-to-leaf path.Run the iterative in-order traversal one step at a time. The stack always holds the path of nodes whose value has not been returned yet, smallest on top. next pops the top node; if it has a right child, push that child and all of its left descendants. hasNext is just "is the stack non-empty".
- pushLeft(node): while node != null, push it and go left.
- Constructor: pushLeft(root).
- next(): node = pop(); pushLeft(node.right); return node.val.
- hasNext(): return the stack is not empty.
class BSTIterator {
private final 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 node = stack.pop();
pushLeft(node.right);
return node.val;
}
public boolean hasNext() {
return !stack.isEmpty();
}
}class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self.pushLeft(root)
def pushLeft(self, node: Optional[TreeNode]) -> None:
while node:
self.stack.append(node)
node = node.left
def next(self) -> int:
node = self.stack.pop()
self.pushLeft(node.right)
return node.val
def hasNext(self) -> bool:
return len(self.stack) > 0class BSTIterator {
vector<TreeNode*> st;
void pushLeft(TreeNode* node) {
while (node) {
st.push_back(node);
node = node->left;
}
}
public:
BSTIterator(TreeNode* root) { pushLeft(root); }
int next() {
TreeNode* node = st.back();
st.pop_back();
pushLeft(node->right);
return node->val;
}
bool hasNext() { return !st.empty(); }
};class BSTIterator {
constructor(root) {
this.stack = [];
this.pushLeft(root);
}
pushLeft(node) {
while (node) {
this.stack.push(node);
node = node.left;
}
}
next() {
const node = this.stack.pop();
this.pushLeft(node.right);
return node.val;
}
hasNext() {
return this.stack.length > 0;
}
}Edge cases to test
- A single node
- A tree that is a chain to the left (h = n) or to the right
- Calling hasNext several times in a row (it must not consume a value)
Hints
Hint 1
The values must come out in sorted order, which for a BST is the in-order traversal.
Hint 2
Flattening the whole traversal into a list works but uses O(n) memory. Can you produce it lazily?
Hint 3
Simulate iterative in-order traversal: keep a stack of the left spine. next pops a node, then pushes the left spine of its right child.
FAQ
What is the best time complexity for Binary Search Tree Iterator?
Optimal (controlled stack of the left spine) runs in O(1) amortized per call time and O(h) extra space. Every node is pushed and popped exactly once over all n calls to next, so the total work is O(n).
Which pattern does Binary Search Tree Iterator use?
It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.
Is there a brute force solution for Binary Search Tree Iterator?
Yes. Brute force (flatten in-order into a list) takes O(n) constructor, O(1) per call time and O(n) space. In the constructor, run an in-order traversal and store every value in a list.
Which edge cases should I test for Binary Search Tree Iterator?
A single node; A tree that is a chain to the left (h = n) or to the right; Calling hasNext several times in a row (it must not consume a value).