Tracing the Iterator

Let’s run the iterator over our tree and look at the stack after each call.

                ╭────╮
                │ 50 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 70 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 40 │      │ 60 │    │ 80 │
╰────╯    ╰────╯      ╰────╯    ╰────╯

Creating the iterator

The constructor pushes the left spine from the root: 50, then 30, then 20, which has no left child. Nothing has been produced yet.

┌────┐
│ 20 │ ◀── top
├────┤
│ 30 │
├────┤
│ 50 │
└────┘

Calling next

next pops 20 and returns it. The right child of 20 is null, so nothing new is pushed. Produced so far: 20.

┌────┐
│ 30 │ ◀── top
├────┤
│ 50 │
└────┘

next pops 30 and returns it. The right child of 30 is 40, so we push its left spine, which is just 40. Produced so far: 20 30.

┌────┐
│ 40 │ ◀── top
├────┤
│ 50 │
└────┘

next pops 40 and returns it. 40 has no right child. Produced so far: 20 30 40.

┌────┐
│ 50 │ ◀── top
└────┘

next pops 50 and returns it. The right child of 50 is 70, so we push its left spine, 70 then 60. Produced so far: 20 30 40 50.

┌────┐
│ 60 │ ◀── top
├────┤
│ 70 │
└────┘

next pops 60 and returns it. 60 has no right child. Produced so far: 20 30 40 50 60.

┌────┐
│ 70 │ ◀── top
└────┘

next pops 70 and returns it. The right child of 70 is 80, so we push its left spine, 80. Produced so far: 20 30 40 50 60 70.

┌────┐
│ 80 │ ◀── top
└────┘

next pops 80 and returns it. 80 has no right child. Produced so far: 20 30 40 50 60 70 80.

(empty stack)

hasNext is now false, so the enhanced for loop ends.

The values came out in sorted order.