Tips for traversing a tree with stacks

 

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. 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.