Iterative preorder on the sample tree, step by step
===================================================

step | action                          | stack (bottom..top) | output so far
1    | pop 1, visit, push its children | [3 2]               | [1]
2    | pop 2, visit, push its children | [3 5 4]             | [1 2]
3    | pop 4, visit, push its children | [3 5]               | [1 2 4]
4    | pop 5, visit, push its children | [3 7]               | [1 2 4 5]
5    | pop 7, visit, push its children | [3]                 | [1 2 4 5 7]
6    | pop 3, visit, push its children | [6]                 | [1 2 4 5 7 3]
7    | pop 6, visit, push its children | [9 8]               | [1 2 4 5 7 3 6]
8    | pop 8, visit, push its children | [9]                 | [1 2 4 5 7 3 6 8]
9    | pop 9, visit, push its children | []                  | [1 2 4 5 7 3 6 8 9]