Step Through a Search Tree One Value at a Time
Solve this ProblemAn iterator over a binary search tree hands out the tree's values one at a time in ascending order. It supports next(), which returns the next smallest value not yet returned, and hasNext(), which tells whether any value is left. Here you are given the tree and a list of calls (1 = next, 0 = hasNext) and must return the answer to each call (a hasNext answer is 1 for true and 0 for false).
Copying the whole tree into a list is easy but uses memory proportional to the number of nodes. A stack that keeps only the pending path uses memory proportional to the height, and each node is still handled only once.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 100 ≤ node.val ≤ 999 (so a value can never be confused with a 0 or 1 answer) - ◆
The tree is a binary search tree (left subtree smaller, right subtree larger), given by its root node - ◆
ops lists calls made on an iterator over the tree's values in ascending order: 1 means next() — return the next smallest value that has not been returned yet; 0 means hasNext() — return 1 if such a value exists, otherwise 0. 0 ≤ ops.length ≤ 60, and next() is never requested when nothing is left - ◆
Return the answers to the calls, in order. The iterator should not have to store all the values: an approach using memory proportional to the tree height h is the target
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Flatten the Tree Into a List First
GoodDo all the work up front: an inorder walk copies every value into a list (ascending), and a position counter remembers how many have been handed out. next() returns the item at the counter and advances it; hasNext() checks that the counter has not reached the end. Every call afterwards is O(1), but the setup walks the whole tree, and the list stores all n values — O(n) memory even if only a few values are ever requested.
O(n) setup, O(1) per callO(n)1class Solution {
2 public List<Integer> runIterator(TreeNode root, int[] ops) {
3 List<Integer> vals = new ArrayList<>();
4 inorder(root, vals);
5 List<Integer> out = new ArrayList<>();
6 int pos = 0;
7 for (int op : ops) {
8 if (op == 1) {
9 out.add(vals.get(pos));
10 pos++;
11 } else {
12 out.add(pos < vals.size() ? 1 : 0);
13 }
14 }
15 return out;
16 }
17
18 private void inorder(TreeNode node, List<Integer> vals) {
19 if (node == null) return;
20 inorder(node.left, vals);
21 vals.add(node.val);
22 inorder(node.right, vals);
23 }
24}Optimal — A Stack Holding Only the Path of Pending Nodes
OptimalKeep a stack that always contains the nodes still "on the way down" to the next value: initially the root and everything down its left edge, so the top is the smallest value. next() pops the top node (that is the next smallest value), and then pushes the left edge of that node's RIGHT child (its subtree holds the values that come right after it). hasNext() is simply "is the stack non-empty?". Each node is pushed and popped exactly once, so all calls together cost O(n) — O(1) amortized per call — and the stack never holds more than the tree's height h nodes.
O(1) amortized per callO(h)1class Solution {
2 public List<Integer> runIterator(TreeNode root, int[] ops) {
3 Deque<TreeNode> stack = new ArrayDeque<>();
4 pushLeft(root, stack);
5 List<Integer> out = new ArrayList<>();
6 for (int op : ops) {
7 if (op == 1) {
8 TreeNode node = stack.pop();
9 out.add(node.val);
10 pushLeft(node.right, stack);
11 } else {
12 out.add(stack.isEmpty() ? 0 : 1);
13 }
14 }
15 return out;
16 }
17
18 private void pushLeft(TreeNode node, Deque<TreeNode> stack) {
19 while (node != null) {
20 stack.push(node);
21 node = node.left;
22 }
23 }
24}