Here are the tips of my solution:
- You always push the root to the stack first
- The most difficult part is: when you see a node on the top of element, should you go on to push its children, or pop it to print it?
- For pre-order traversal, you can pop it then push their children.
- For in-order traversal, you need to check whether its left child has been popped yet. If yes, pop it; else, push its left child.
- You can add a flag to the node when it is pushed to stack with initial value equals to False.
- Enquiry this flag before deciding whether to pop current node. If True, do a pop; If False, set this flag as True before pushing its left child.
- You should set the flag to True even if its left child is Null
- For post-order traversal, you need to check whether both its children have been popped yet. This time you need two flags.