Tree Traversal
Just like we needed to know how to traverse a Linked List, we need to know how to traverse a Tree. In a Linked List, the work we were doing to each Node could come either before or after the recursive call; this determined whether that work was done from the front of the list to the back, or from the back to the front. We have a similar concept here for trees, we just have more options.
Preorder Traversal: In preorder traversal, we have the rule that the node we're looking at must be visited before its children; there are no rules as to the order of its children, or grandchildren. In the following code, I'm going to use visit() in place of whatever work you're doing to each node (maybe you're printing each data point, or whatever). Preorder traversal looks like this:
preorder(Node n) {
visit(n)
for each child c of n:
preorder(c)
}
Postorder Traversal: In postorder traversal, the node we're looking at is visit after its children. It looks like this:
postorder(Node n) {
for each child c of n:
postorder(c)
visit(n)
}
Inorder Traversal: We're going to deal with a lot of binary trees in this class. With a binary tree, we also have the option of Inorder Traversal, which is where you visit the left subtree first, then this node, then the right subtree.
inorder(Node n) {
inorder(n.left)
visit(n)
inorder(n.right)
}
Consider the following tree:
These traversals would visit the nodes in the following order:
Preorder: A B C D F E
Inorder: B A F D C E
Postorder: B F D E C A