Tree Traversals
This page demonstrates the standard tree traversals (or tree walks):
- Preorder traversals visit a node and then (recursively)
traverse its children.
- Postorder traversals traverse a node's children and then
visit the node.
- Inorder traversals traverse a node's first child (if any),
then visit the node, then traverse its other children. Generally, the term
applies only to binary trees.
- Breadth-first traversals (also called level-order traversals when applied to trees) traverse all nodes at each successive
depth (distance from the root).
- Iterative deepening is a technique for performing a
breadth-first search by a series of postorder traversals that stop at
increasing depths. First all depth-0 nodes are visited, then all
depth-one, etc. It has the advantage of avoiding a queue of pending nodes
in exchange for a decrease in speed (a constant factor is most nodes have
more than one child).
Here, the term visit generically refers to some processing applied to
each node, depending on what the traversal is being used to accomplish.
The traversals below (under the Actions menu) number the nodes
in the order they are visited. As the traversals progress, a node is tinted
green to indicate that the subtree rooted at that node is being traversed,
blue to indicate that it is being visited, and (for breadth-first search)
orange to indicate it has been placed in a queue of nodes to be processed.
You may enter trees in Lisp notation (in the Tree: area), or you
can generate a random tree with the Actions->Random tree menu button.