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); result.add(root); 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