What are the inorder, preorder and postorder traversals of a binary tree, and what does each one tell you?
They are three ways of walking a binary tree, and the names say where the root is visited in relation to the two sub-trees.
the name the order of the work
-------------- --------------------------------------------
preorder root, then the left tree, then the right tree
inorder left tree, then the root, then the right tree
postorder left tree, then the right tree, then the root
level order level by level from the top, left to right
So what does each one tell you? This is the useful part.
An inorder traversal of a binary search tree gives you the values in increasing order. That is the main reason inorder is worth knowing, because you can sort the values of a search tree by walking it in order.
A preorder traversal gives you a copy of the tree. If you write the values down as you go, you can build the tree again from the values, because you know where each root is and what comes after it. That is how you can copy a tree or serialise it.
A postorder traversal gives you the children before the parent. That is what you want when you are deleting a tree, because you have to delete the children before you delete the parent. It is also what you want when you are calculating the height, because the height of a node is one plus the bigger of the heights of its children.
the tree 8
/ \
3 10
/ \ \
1 6 14
inorder 1, 3, 6, 8, 10, 14
preorder 8, 3, 1, 6, 10, 14
postorder 1, 6, 3, 14, 10, 8
And a level order traversal gives you the tree level by level. That is useful when you want to see the shape of the tree, and it is the only one of the four that is not a depth first walk.
So the rule to remember is this. Inorder sorts a search tree, preorder copies a tree, and postorder deletes a tree or measures it.
The last question in this topic shows the code for the three depth first walks.