December 2009
Intermediate to advanced
380 pages
9h 2m
English
When we talk about visiting a tree, we mean executing some actions on the nodes of a tree. The order in which we traverse the nodes is important because that affects the order in which we execute the actions. There are three key traversals:
Preorder traversal or top-down traversal: + 1 2. Visit a (parent) node before visiting its children.
Inorder traversal: 1 + 2. Visit a node in between visiting children.
Postorder traversal or bottom-up traversal: 1 2 +. Visit a node after visiting its children.
Humans can pick out tree traversals by looking at a tree and, perhaps, tapping a pen on the nodes in a particular sequence. To implement this in code, we typically use a tree-walking algorithm called depth-first search ...