# Binary Search Tree Iterator

## Yielding and Binary Tree Inorder Traversal

In the problem Binary Tree Inorder Traversal, we solved it by simlating the function call.

Only a bit different this time,
when the caller calls `next()`

:

- just execute to next value returns
- save the stack and next address (state)
- yield the node value and return control to caller

actions above is the `while`

body part in the Binary Tree Inorder Traversal.

### Edge cases in `hasNext()`

like Binary Tree Inorder Traversal, when the stack is empty, there are no more nodes.

However, if only one state left in the stack and the address of the state is `POST`

,
we need some additional check.

`POST`

state here means to deal with right node of current node (value already yeild to caller when `IN`

step).
sometimes, the node does not have right child. we should return false when caller ask `hasNext()`

.

## Why it is `O(h)`

in space

the space here used in my solution is the `stack`

.
only tree nodes with left child will consume a space in the `stack`

.
because nodes without left child can be yield to caller directly.

Worst case

```
1
/
2
/
3
```

here we have to save `node 1`

and `node 2`

before we found `node 3`

.
but the space used in stack will be no more than 3.

### Source code *Read on Github*

```
1 /**
2 * Definition for binary tree
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10
11 public class BSTIterator {
12
13 static enum ReturnAddress {
14 PRE, IN, POST, DONE;
15 }
16
17 static class StackState {
18 ReturnAddress returnAddress = ReturnAddress.PRE;
19 TreeNode param;
20
21 StackState(TreeNode param){
22 this.param = param;
23 }
24 }
25
26 Deque<StackState> stack = new LinkedList<StackState>();
27
28 public BSTIterator(TreeNode root) {
29 if(root != null) {
30 stack.push(new StackState(root));
31 }
32 }
33
34 /** @return whether we have a next smallest number */
35 public boolean hasNext() {
36 if(!stack.isEmpty()){
37 StackState current = stack.pop();
38 switch(current.returnAddress){
39 case PRE:
40 case IN:
41 stack.push(current);
42 return true;
43
44 case POST:
45 if(current.param.right != null){
46 stack.push(new StackState(current.param.right));
47 return true;
48 }
49 }
50 return hasNext();
51 }
52 return false;
53 }
54
55 /** @return the next smallest number */
56 public int next() {
57
58 StackState current = stack.pop();
59 switch(current.returnAddress){
60 case PRE:
61 current.returnAddress = ReturnAddress.IN;
62
63 if(current.param.left != null){
64 stack.push(current);
65 stack.push(new StackState(current.param.left));
66 break;
67 }
68
69 case IN:
70 current.returnAddress = ReturnAddress.POST;
71 stack.push(current);
72 return current.param.val;
73
74 case POST:
75 current.returnAddress = ReturnAddress.DONE;
76
77 if(current.param.right != null){
78 stack.push(current);
79 stack.push(new StackState(current.param.right));
80 break;
81 }
82 }
83 return next();
84 }
85 }
86
87 /**
88 * Your BSTIterator will be called like this:
89 * BSTIterator i = new BSTIterator(root);
90 * while (i.hasNext()) v[f()] = i.next();
91 */
```