Visiting a tree: pre, in and post order
Build a binary search tree of seven numbers and walk it four ways: in-order, pre-order, post-order and level by level. See four different orders of the same numbers, why in-order comes out sorted, and how a queue walks the tree row by row.
Core concept
A traversal visits every node of a tree once; pre-order visits a node before its children, in-order between its left and right children, post-order after them, and level order row by row with a queue
Topic: Data structures
To print or copy a tree, a program has to visit every node once, and there is more than one way to do it. Each way is a small recursive rule. Pre-order visits the node first, then its left side, then its right side: the root comes first, which is the order you would use to copy the tree. In-order visits the left side, then the node, then the right side: in a binary: Counting with only two digits, 0 and 1. Computers store everything this way. All key words search tree that prints the numbers from smallest to largest. Post-order visits the left side, then the right side, then the node last: children always come before their parent, which is the order you would use to delete a tree safely. Level order is different: it uses a queue to visit the tree row by row, from the root downwards, left to right.
What you will learn
- Walk a binary tree in pre-order, in-order and post-order.
- Explain why an in-order walk of a binary search tree is sorted.
- Use a queue to walk a tree level by level.
- Predict the order of a walk before running it.
Before you start
- Know what a binary search tree is (smaller numbers left, bigger right).
Materials
- Paper to draw the tree and number the visits
Equipment
- None
Procedure
- Run the in-order walk and read the output.
- Run the pre-order and post-order walks of the same tree.
- Run the level-order walk and watch the queue.
- Answer the practice challenges.