Binary Trees Summary

Traversing a tree - INORDER
Using this method, we must visit the tree in this order:
Visit the left sub-tree.
Visit the root node.
Visit the right sub-tree.
How does this work? We visit the left sub-tree, then the node, then the right sub-tree.

We start at the root, node A.
Underneath node A is the left sub-tree (with root node B) and the right sub-tree (with root node C).
We must check the left sub-tree first according to our INORDER rules. Move to B.
But B has a left sub-tree (with a root at D) and a right sub-tree (with a root at E).
We must check the left sub-tree first according to our INORDER rules. Move to D.
D does not have a left sub-tree, so visit the node D.
Now check for D’s right sub-tree. It doesn’t have one.
We have now done the left sub-tree for the tree that has a root node at B. Now visit node B.
Now visit the right sub-tree of B. We move to E.
E doesn’t have a left sub-tree so visit E.
E doesn’t have a right sub-tree so move to B and because we have now completely visited the tree with the root node at B, we move up to node A. Visit node A.
Now visit the right sub-tree of A. We move to C.
C doesn’t have a left sub-tree so visit C.
C doesn’t have a right sub-tree so move back up to A.
We have now visited every node.
The order that we visited the nodes was DBEAC. We can write an algorithm to print out all of the data at the nodes, like this:
1.For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 2. If there isn’t, go to 3.
2.Repeat 1.
3.Print the current node.
4.For the current node, check whether it has a right sub-tree. If it has, go to 5. else go to 6.
5.Repeat 1.
6.END
20.5.2 Traversing a tree - PREORDER
Using this method, we need to
Visit the root node.
Visit the left sub-tree.
Visit the right sub-tree.
Using our previous binary tree, we would visit the nodes in the order: A B D E C. We can write an algorithm that would print out all of the data at the nodes, like this:
1.Print the current node.
2.For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 1. If there isn’t, go to 3.
3.For the current node, check whether it has a right sub-tree. If it has, go to 4. else go to 5.
4.Repeat 1.
5.END.
Traversing a tree - POSTORDER
Using this method, we need to
Visit the left sub-tree.
Visit the right sub-tree.
Visit the root node.