Computer Neek

What are binary tree traversals.

Binary tree traversals are a way of visiting each node in a binary tree.

Inorder tree traversals

The three aspects of this traversal are Left, Visit, and Right. This means that you should start by visiting the node, then traverse (move) left and then right. Look at the tree below. First, we've annotated each node with L, V, R. A way to remember that is that the letter V is in the middle and the letters L and R are in alphabet order of letters; L first then R.

We always begin with the root node which is 9. We go left to 7 and left again to 6 and left one more time to 5 whilst simultaneously crossing the L's. We then visit node 5 and cross the V of node 5. Since it also has no children, we can also cross off its R.

We then traverse back up since it has no children and visit node 6 whilst crossing off V. Since node 6 has no children we cross R and traverse to node 7 and visit it. As a result, we cross off V on node 7 and traverse to its right node. Since it has no children, we can't traverse left so we visit it and we also can’t traverse right so we go back up to node 7 after crossing off all its letters.

We now traverse upwards to node 9, visit it and traverse to the right child node after crossing off V and R. We are now at node 11. From here we traverse to the left to node 10 and cross L on node 11. Since node 10 has no child nodes, we can cross L, visit the node, cross off V and R. We then traverse back up to node 11, since it has no right child nodes, we can cross off R. We have now traversed through all the nodes.

Postorder traversal

This traversal has three aspects: left, right, and visit. This means, traverse left, then right and finally visit the node. Look at the tree below. First, we labeled each node with L, R, V. A good way to remember that this is the order of traversals is that "the postman LEFT you the package because your neighbor on the RIGHT was not in when he VISITED.”

We always start with the root node which is 9. We go left to 7 and left again to 6 and left one more time to 5. Because node 5 has no more children, you cross out the L's of all the nodes you've passed through, as well as the L, R, and V of 5.

You go back to node 6 and cross out R and then back up to 7 and cross the R before traversing to node 8. Since node 8 has no child nodes, you cross L, R, and V of node 8 and visit it. You go back to node 7 and visit that too.

Since node 7 has no unvisited child nodes, you traverse back to node 9 and go right. You are now at node 11. You traverse left to node 10 but since node 10 has no child nodes, you cross L, R, and V and visit it.

Finally, you traverse back up to node 11. Since node 11 has no right child node, you cross R and V and visit it. You then traverse back up to node 9 and visit it.

Preorder Traversal

This traversal has three features: visit, left, and right. This means, visit the node, then traverse right and then traverse left. Look at the tree below. First, we have annotated each node with V, R, L.

We always start with the root node which is 9. We visit node 9 and traverse left after crossing the V and L from node 9. Since we traversed left, we are now at node 7. We then visit node 7 and traverse left and keep doing so till we reach node 5. We cross V and L after every traversal. From node 5, since it has no child nodes, we can cross off V, L, and R from it.

We now traverse back up to 7 since it's the closest one with child nodes. From there we traverse right, cross R from node 7 and since we are at node 8 and it has no child nodes, we cross off V, L, and R.

Now we traverse back to node 7 and then back up again to node 9 since node 7 has no unvisited child nodes. From node 9 we cross R from node 9 and traverse right to node 11. We then visit node 11 and traverse left to node 10 after crossing V and L from it. Now that we are at node 10, we visit it and cross V from it. Since it has no child nodes, we also cross L and R and traverse back to node 11 and cross R from it and traverse back to the root node. We have now completed the traversal.

Summary

Postorder: L, R, V

Preorder: V, L, R

Inorder: L, V, R

Click here to learn about graph traversal.

To read about trees and a binary tree click here