# Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

• Elements are visited in ascending order (i.e. an in-order traversal)
• `next()` and `hasNext()` queries run in O(1) time in average.

Example

For the following binary search tree, in-order traversal by using iterator is `[1, 6, 10, 11, 12]`

```   10
/    \
1      11
\       \
6       12```

Challenge

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

1. Inorder Traverse the BST into an arrayList – O(n) space and O(n) time

```public class Solution {
//@param root: The root of binary tree.
ArrayList<TreeNode> nodes;
int index;
public Solution(TreeNode root) {
//flattern the tree using in-order traversal
nodes = new ArrayList<>();
inOrderTraversal(root, nodes);
index = 0;
}

public void inOrderTraversal(TreeNode root, ArrayList<TreeNode> result) {
if (root == null) {
return;
}
inOrderTraversal(root.left, result);
inOrderTraversal(root.right, result);
}

//@return: True if there has next node, or false
public boolean hasNext() {
return index < nodes.size();
}

//@return: return next node
public TreeNode next() {
if (index < nodes.size()) {
return nodes.get(index++);
}
return null;
}
}```

2. O(h) space – h is the height of the tree
Have a stack which only contains the left-most nodes and its ancestors, so that it takes O(h) space. And for each node, the average time complexity for next() is O(1).(Since the total time complexity is O(n))

```public class Solution {
//@param root: The root of binary tree.
Stack<TreeNode> nodes;
public Solution(TreeNode root) {
nodes = new Stack<>();
TreeNode runner = root;
while (runner != null) {
nodes.push(runner);
runner = runner.left;
}
}

//@return: True if there has next node, or false
public boolean hasNext() {
return !nodes.empty();
}

//@return: return next node
public TreeNode next() {
if (!nodes.empty()) {
TreeNode curr = nodes.pop();
if (curr.right != null) {
TreeNode runner = curr.right;
while (runner != null) {
nodes.push(runner);
runner = runner.left;
}
}
return curr;
}
return null;
}
}```

3. O(1) space