Implement a preorder iterator for a Binary Tree, need to be O N time and space needs to be less than O(N) or O(1).

it needs to have the next and hasNext method.

Similar question: https://leetcode.com/problems/binary-search-tree-iterator/