Preorder, Inorder, and Postorder Traversal of a Tree

Published , Updated

The following post is derived from notes taken while reading through this textbook .

Some of the terms used in this post have been defined here.

For the purpose of this post, we will be using the tree above. Each node of the tree holds a color and, for our traversal, we will pretend that the names of these colors are being printed as a loop traverses the tree in whichever way is being discussed. We will also assume that the traversals all start at the root-node.

Click here to see the pseudocode for both a recursive, and iterative, preorder traversal.

Preorder Traversal:

The preorder traversal works on the concept of Node-Left-Right. If we apply a preorder traversal algorithm to the example tree, we will be given the following output.

Red, Purple, Orange, Yellow, and Green.

  1. The algorithm prints the color of the current node. This color is Red.
  2. Then it checks if the current node has a left node.
  3. The algorithm finds a left node.
  4. The algorithm traverses to the left node.
  5. The algorithm prints the color of the current node. This color is Purple.
  6. Then it checks if the current node has a left node.
  7. The algorithm finds a left node.
  8. The algorithm traverses to the left node.
  9. The algorithm prints the color of the current node. This color is Orange.
  10. The algorithm checks if the current node has a left node.
  11. The algorithm doesn't find a left node.
  12. The algorithm checks if the current node has a right node.
  13. The algorithm finds no right node.
  14. The algorithm returns to the previous node.
  15. The algorithm checks if the current node has a right node.
  16. The algorithm finds a right node.
  17. The algorithm traverses to the right nod.
  18. The algorithm prints the color of the current node. This color is Yellow.
  19. Then it checks if the current node has a left node.
  20. The algorithm finds no left node.
  21. The algorithm checks if the current node has a right node.
  22. The algorithm finds no right node.
  23. The algorithm returns to the previous node.
  24. The algorithm checks if the current node has a right node.
  25. The algorithm finds a right node.
  26. The algorithm traverses to the right node.
  27. The algorithm prints the color of the current node. This color is Green.
  28. Then it checks if the current node has a left node.
  29. The algorithm finds no left node.
  30. The algorithm checks if the current node has a right node.
  31. The algorithm finds no right node.
  32. The algorithm returns to the previous node.
  33. The algorithm has no more nodes to go back to.
  34. The algorithm is finished.

Inorder Traversal:

The inorder traversal works on the concept of Left-Node-Right. If we apply an inorder traversal algorithm to the example tree, we will be given the following output.

Orange, Purple, Yellow, Red, and Green.

  1. The algorithm checks if the current node has a left node.
  2. The algorithm finds a left node.
  3. The algorithm traverses to the left node.
  4. The algorithm checks if the current node has a left node.
  5. The algorithm finds a left node.
  6. The algorithm traverses to the left node.
  7. The algorithm checks if the current node has a left node.
  8. The algorithm doesn't find a left node.
  9. The algorithm prints the color of the current node. This color is Orange.
  10. The algorithm checks if the current node has a right node.
  11. The algorithm doesn't find a right node.
  12. The algorithm returns to the previous node.
  13. The algorithm prints the color of the current node. This color is Purple.
  14. The algorithm checks if the current node has a right node.
  15. The algorithm finds a right node.
  16. The algorithm traverses to the right node.
  17. The algorithm checks if the current node has a left node.
  18. The algorithm doesn't find a left node.
  19. The algorithm prints the color of the current node. This color is Yellow.
  20. The algorithm checks if the current node has a right node.
  21. The algorithm doesn't find a right node.
  22. The algorithm returns to the previous node.
  23. The algorithm returns to the previous node.
  24. The algorithm prints the color of the current node. This color is Red.
  25. The algorithm checks if the current node has a right node.
  26. The algorithm finds a right node.
  27. The algorithm traverses to the right node.
  28. The algorithm checks if the current node has a left node.
  29. The algorithm doesn't find a left node.
  30. The algorithm prints the color of the current node. This color is Green.
  31. The algorithm checks if the current node has a right node.
  32. The algorithm doesn't find a right node.
  33. The algorithm returns to the previous node.
  34. The algorithm has no more nodes to go back to.
  35. The algorithm is finished.

Postorder Traversal:

The postorder traversal works on the concept of Left-Right-Node. If we apply a postorder traversal algorithm to the example tree, we will be given the following output.

Orange, Yellow, Purple, Green, and Red.

  1. The algorithm checks if the current node has a left node.
  2. The algorithm finds a left node.
  3. The algorithm traverses to the left node.
  4. The algorithm checks if the current node has a left node.
  5. The algorithm finds a left node.
  6. The algorithm traverses to the left node.
  7. The algorithm checks if the current node has a left node.
  8. The algorithm doesn't find a left node.
  9. The algorithm checks if the current node has a right node.
  10. The algorithm doesn't find a right node.
  11. The algorithm prints the color of the current node. This color is Orange.
  12. The algorithm returns to the previous node.
  13. The algorithm checks if the current node has a right node.
  14. The algorithm finds a right node.
  15. The algorithm traverses to the right node.
  16. The algorithm checks if the current node has a left node.
  17. The algorithm doesn't find a left node.
  18. The algorithm checks if the current node has a right node.
  19. The algorithm doesn't find a right node,.
  20. The algorithm prints the color of the current node. This color is Yellow.
  21. The algorithm returns to the previous node.
  22. The algorithm prints the color of the current node. This color is Purple.
  23. The algorithm has already finished with this node.
  24. The algorithm returns to the previous node.
  25. The algorithm checks if the current node has a right node.
  26. The algorithm finds a right node.
  27. The algorithm traverses to the right node.
  28. The algorithm checks if the current node has a left node.
  29. The algorithm doesn't find a left node.
  30. The algorithm checks if the current node has a right node.
  31. The algorithm doesn't find a right node.
  32. The algorithm prints the color of the current node. This color is purple.
  33. The algorithm returns to the previous node.
  34. The algorithm prints the color of the current node. This color is red.
  35. The algorithm has no more nodes to go back to.
  36. The algorithm is finished.