This is the order in which you would want to transverse to read the chapters of a book.
Like breadth-first search, this also has the property of visiting parents before any children.
This is the easiest one to do iteratively:
  • pop and visit
  • push right to stack
  • push left to stack
This is the order in which a binary search tree should be traversed for ordered output, i.e.:
  • everything to the left is smaller than parent
  • everything to the right is larger than parent
This ordering makes sense for binary trees and not k-ary trees in general because if there are more than two nodes it is not clear what the top node should go in the middle of.
This is unlike pre-order depth-first search and post-order depth-first search which generalize obviously to general trees.
This is a bit harder than iterative pre-order: now we have to check if there is a left or right element or not:
  • (START) push current
  • if there is left:
    • move left
  • else:
    • (ELSE) pop
    • visit
    • if there is right
      • move right
      • GOTO START
    • else:
      • GOTO ELSE
The control flow can be slightly simplified if we allow NULLs: www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
Has the property of visiting all descendants before the parent.
This is the hardest one to do iteratively.
Bibliography:
www.geeksforgeeks.org/iterative-postorder-traversal/
www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Articles by others on the same topic (1)

See all articles in the same topic