Interview
Interview Guide
Coding Problems List
Problems

# 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.