Sample tree: every traversal, recursive and iterative
=====================================================

tree (value(left,right), - = no child): 1(2(4,5(7,-)),3(-,6(8,9)))

recursive inorder        : [4, 2, 7, 5, 1, 3, 8, 6, 9]
recursive preorder       : [1, 2, 4, 5, 7, 3, 6, 8, 9]
recursive postorder      : [4, 7, 5, 2, 8, 9, 6, 3, 1]

iterative inorder        : [4, 2, 7, 5, 1, 3, 8, 6, 9]
iterative preorder       : [1, 2, 4, 5, 7, 3, 6, 8, 9]
iterative postorder (2 stacks): [4, 7, 5, 2, 8, 9, 6, 3, 1]
iterative postorder (1 stack) : [4, 7, 5, 2, 8, 9, 6, 3, 1]

Morris inorder           : [4, 2, 7, 5, 1, 3, 8, 6, 9]
Morris preorder          : [1, 2, 4, 5, 7, 3, 6, 8, 9]
tree after Morris        : 1(2(4,5(7,-)),3(-,6(8,9)))  (unchanged)

level order (queue)       : [1, 2, 3, 4, 5, 6, 7, 8, 9]
level order by level      : [[1], [2, 3], [4, 5, 6], [7, 8, 9]]
zigzag                    : [[1], [3, 2], [4, 5, 6], [9, 8, 7]]