# Tree traversal

The summary from www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ is a winner:
``````    1
/ \
2   3
/ \
4   5``````
In principle one could talk about tree traversal of unordered trees as a number of possible traversals without a fixed order. But we won't consider that under this section, only deterministic ordered tree traversals.
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.

## Iterative pre-order

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.

## Iterative in-order

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.

## Iterative post-order

This is the hardest one to do iteratively.

## Iterative post-order with two stacks

www.geeksforgeeks.org/iterative-postorder-traversal/

## Iterative post-order with one stack

www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

##  Ancestors

View article source