Tree Traversals

Nicholas Duchon: Apr 17, 2018.

Outline



The Wiki has a nice article:

Example

Here's a fairly simple example:

X in-order:
  5 10 15 20 25 30 35 40 45 50 55 60 65 70 75
X pre-order:
  40 20 10 5 15 30 25 35 60 50 45 55 70 65 75
X post-order:
   5 15 10 25 35 30 20 45 55 50 65 75 70 60 40
X level-order:
  40 20 60 10 30 50 70 5 15 25 35 45 55 65 75
Here are the basic algorithms:

In order, recursive

visit left node
visit this node
visit right node

Pre order, recursive

visit this node
visit child nodes

Post order - recursive

visit child nodes
visit this node

Level order = breadth first - best using a queue (FIFO):

enqueue root
while queue not empty
  node = dequeue
  visit node
  enqueue child nodes
end while

Depth first - best using a stack (LIFO):

push root
while stack not empty
  node = pop
  push child nodes
  visit node
end while
Level-order implements a breadth-first ordering of a tree or a graph (if you add code to make sure nodes are only visited once).

Note also that pre, post and level order make sense in any tree, but in-order only makes sense in a BINARY tree.


ND.