Recursion
Traversal Order
Without writing code, determine the preorder traversal, inorder traversal, and postorder traversal of the following tree.
Hint: is there a fast way to do this?
Here's a trick to finding the preorder traversal: draw a flag to the left of every node and trace through a path, going counterclockwise.
You get that the preorder traversal order is [A, B, D, E, F, G, C]
You can do something similar for inorder and postorder traversals,
Inorder traversal = [D, B, F, E, G, A, C]
Postorder traversal = [D, F, G, E, B, C, A]
Why this trick works (optional):
The preorder, inorder, and postorder traversals are more similar than you might think - they actually all visit each node in the same exact order. This is indicated by the yellow line, which is the same for all of them. The only difference between these traversals is the order that print gets called inside of each traversal function.
A flag to the left indicates that we call print immediately when we enter the current node. This is a preorder traversal.
A flag to the right means we're calling print on the current node, after we've visited all of the children nodes. This is a postorder traversal.
A flag below means we call print after visiting all the left children, and before visiting all the right children. This is an inorder traversal.