```
public class BSTIterator {
private TreeNode current;
public BSTIterator(TreeNode root) {
TreeNode fake = new TreeNode(0);
fake.right = root;
TreeNode tail = fake;
TreeNode rest = tail.right;
while (rest != null) {
if (rest.left == null) {
tail = rest;
rest = rest.right;
} else {
TreeNode tmp = rest.left;
rest.left = tmp.right;
tmp.right = rest;
rest = tmp;
tail.right = tmp;
}
}
this.current = fake.right;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return current != null;
}
/** @return the next smallest number */
public int next() {
try {
return current.val;
} finally {
current = current.right;
}
}
```

}

But it is **destructive**.

Based on https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm