Binary Search Tree Iterator

Problem

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

Solution

Use a stack.

We need a helper function push(node) to add nodes to the stack. When it is called, keep adding the node and its left child until there's no left child. Call push(root) to initialize the stack.

When next() of the iterator is called, return the top of the stack and call push() on its right node.

For the example above, we first push() the root node 10 to the stack

[10]

Then its left node 1:

[1 10]

Now if we call next(), it will return 1 and add the right node 6 to the stack:

[6 10]

Call next() again, it will return 6 and since it does not have a right child, it will not add any node to the stack.

[10]

Call next() again, it will return 10 and push() the right node 11 to the stack.

[11]

And similarly the next next() call will return 11 and add 12 to the stack.

hasNext() just checks if the stack is empty.