CP164 Study Guide - Final Guide: Preorder, The Algorithm
Inorder, Preorder, Postorder, Levelorder Traversals
In the example above of the count method, the order in which the tree nodes are traversed makes
no difference. We could walk through the tree by recursing through the right children rather than
the left children first, and the resulting count would be the same. However, there are some
traversal orders that give us information about the data stored in the tree, or tell us something
about the order in which data was stored in the tree.
Inorder Traversal
Inorder traversal allows us to walk through the tree and access node data in order - by that we
mean we can either print or extract (i.e. copy the data to an array) the data in value order. For our
sample tree, and inorder traversal would give us the data back in the following order:
6, 7, 8, 9, 11, 12, 15, 18
In short, we are retrieving the tree data in order, thus the name of the traversal. This makes BSTs
extremely powerful in terms of doing things like sorting data.
The inorder algorithm is very simple:
• Attempt to visit a node. If the node is not None:
• Visit the node's left child
• Print or extract the data.
• Visit the node's right child
Preorder Traversal
Preorder is just as simple:
• Attempt to visit a node. If the node is not None:
• Print or extract the data.
• Visit the node's left child
• Visit the node's right child
Thus the data in our sample tree would be printed or extracted in preorder as:
11, 7, 6, 9, 8, 15, 12, 18
Preorder is useful in that if we insert data into a BST in preorder, we will produce a tree with a
structure identical to that of the tree that we extracted the data from. Try it with the preorder data
above: you should end up with a tree that looks the same as the tree at the top of these notes.
Postorder Traversal
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
In the example above of the count method, the order in which the tree nodes are traversed makes no difference. We could walk through the tree by recursing through the right children rather than the left children first, and the resulting count would be the same. However, there are some traversal orders that give us information about the data stored in the tree, or tell us something about the order in which data was stored in the tree. Inorder traversal allows us to walk through the tree and access node data in order - by that we mean we can either print or extract (i. e. copy the data to an array) the data in value order. For our sample tree, and inorder traversal would give us the data back in the following order: In short, we are retrieving the tree data in order, thus the name of the traversal.
