In computer science, tree traversal refers to the process of visiting each node in a
tree data structure, exactly once, in a systematic way. Such traversals are classified by the
order in which the nodes are visited. The following algorithms are described for a binary
tree, but they may be generalized to other trees as well.
Types
Compared to linear data structures like linked lists and one-dimensional arrays, which have
a canonical method of traversal, tree structures can be traversed in many different ways. Starting
at the root of a binary tree, there are three main steps that can be performed and the order
in which they are performed defines the traversal type. These steps are: performing an action
on the current node, traversing to the left child node, and traversing to the right child
node. Traversing a tree involves iterating over
all nodes in some manner. Because from a given node there is more than one possible next
node, then, assuming sequential computation, some nodes must be deferred – stored in
some way for later visiting. This is often done via a stack or queue. As a tree is a
self-referential data structure, traversal can naturally be described by recursion or,
more subtly, corecursion, in which case the deferred nodes are stored implicitly – in
the case of recursion, in the call stack. The name given to a particular style of traversal
comes from the order in which nodes are visited. Most simply, does one go down first or across
first? Depth-first traversal is further classified by position of the root element with regard
to the left and right nodes. Imagine that the left and right nodes are constant in space,
then the root node could be placed to the left of the left node, between the left and
right node, or to the right of the right node. There is no equivalent variation in breadth-first
traversal – given an ordering of children, "breadth-first" is unambiguous.
For the purpose of illustration, it is assumed that left nodes always have priority over
right nodes. This ordering can be reversed as long as the same ordering is assumed for
all traversal methods. Depth-first traversal is easily implemented
via a stack, including recursively, while breadth-first traversal is easily implemented
via a queue, including corecursively. Beyond these basic traversals, various more
complex or hybrid schemes are possible, such as depth-limited searches such as iterative
deepening depth-first search. Depth-first
There are three types of depth-first traversal: pre-order, in-order, and post-order. For a
binary tree, they are defined as operations recursively at each node, starting with the
root node as follows: Pre-order
Visit the root. Traverse the left subtree.
Traverse the right subtree. In-order
Traverse the left subtree. Visit the root.
Traverse the right subtree. Post-order
Traverse the left subtree. Traverse the right subtree
Visit the root
The trace of a traversal is called a sequentialisation of the tree. No one sequentialisation according
to pre-, in- or post-order describes the underlying tree uniquely. Given a tree with distinct
elements, either pre-order or post-order paired with in-order is sufficient to describe the
tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.
Generic tree To traverse any tree in depth-first order,
perform the following operations recursively at each node:
Perform pre-order operation For each i do:
Visit i-th, if present Perform in-order operation
Visit n-th child, if present Perform post-order operation
where n is the number of child nodes. Depending on the problem at hand, the pre-order, in-order
or post-order operations may be void, or you may only want to visit a specific child node,
so these operations are optional. Also, in practice more than one of pre-order, in-order
and post-order operations may be required. For example, when inserting into a ternary
tree, a pre-order operation is performed by comparing items. A post-order operation may
be needed afterwards to re-balance the tree. Breadth-first
Trees can also be traversed in level-order, where we visit every node on a level before
going to a lower level. Applications
Pre-order traversal while duplicating nodes and edges can make a complete duplicate of
a binary tree. It can also be used to make a prefix expression from expression trees:
traverse the expression tree pre-orderly. In-order traversal is very commonly used on
binary search trees because it returns values from the underlying set in order, according
to the comparator that set up the binary search tree.
Post-order traversal while deleting or freeing nodes and values can delete or free an entire
binary tree. It can also generate a postfix representation of a binary tree.
Implementations Depth-first
Pre-order In-order
Post-order All the above implementations require call
stack space proportional to the height of the tree. In a poorly balanced tree, this
can be considerable. We can remove the stack requirement by maintaining parent pointers
in each node, or by threading the tree. Morris in-order traversal using threading
A binary tree is threaded by making every left child pointer point to the in-order predecessor
of the node and every right child pointer point to the in-order successor of the node.
Advantages: Avoids recursion, which uses a call stack
and consumes memory and time. The node keeps a record of its parent.
Disadvantages: The tree is more complex.
It is more prone to errors when both the children are not present and both values of nodes point
to their ancestors. Morris traversal is an implementation of in-order
traversal that uses threading: Create links to the in-order successor
Print the data using these links Revert the changes to restore original tree.
Breadth-first Also, listed below is pseudocode for a simple
queue based level order traversal, and will require space proportional to the maximum
number of nodes at a given depth. This can be as much as the total number of nodes / 2.
A more space-efficient approach for this type of traversal can be implemented using an iterative
deepening depth-first search.
levelorder(root) q = empty queue
q.enqueue(root) while not q.empty do
node := q.dequeue() visit(node)
if node.left ≠ null then q.enqueue(node.left)
if node.right ≠ null then q.enqueue(node.right)
Infinite trees While traversal is usually done for trees
with a finite number of nodes it can also be done for infinite trees. This is of particular
interest in functional programming, as infinite data structures can often be easily defined
and worked with, though they are not evaluated, as this would take infinite time. Some finite
trees are too large to represent explicitly, such as the game tree for chess or go, and
so it is useful to analyze them as if they were infinite.
A basic requirement for traversal is to visit every node. For infinite trees, simple algorithms
often fail this. For example, given a binary tree of infinite depth, a depth-first traversal
will go down one side of the tree, never visiting the rest, and indeed if in-order or post-order
will never visit any nodes, as it has not reached a leaf. By contrast, a breadth-first
traversal will traverse a binary tree of infinite depth without problem, and indeed will traverse
any tree with bounded branching factor. On the other hand, given a tree of depth 2,
where the root node has infinitely many children, and each of these children has two children,
a depth-first traversal will visit all nodes, as once it exhausts the grandchildren, it
will move on to the next. By contrast, a breadth-first traversal will never reach the grandchildren,
as it seeks to exhaust the children first. A more sophisticated analysis of running time
can be given via infinite ordinal numbers; for example, the breadth-first traversal of
the depth 2 tree above will take ?·2 steps: ? for the first level, and then another ? for
the second level. Thus, simple depth-first or breadth-first
searches do not traverse every infinite tree, and are not efficient on very large trees.
However, hybrid methods can traverse any infinite tree, essentially via a diagonal argument.
Concretely, given the infinitely branching tree of infinite depth, label the root node
the children of the root node the grandchildren and so on. The nodes are thus in a one-to-one
correspondence with finite sequences of positive numbers, which are countable and can be placed
in order first by sum of entries, and then by lexicographic order within a given sum,
which gives a traversal. Explicitly:
0: 1:
2: 3:
4:
etc. This can be interpreted as mapping the infinite
depth binary tree onto this tree and then applying breadth-first traversal: replace
the "down" edges connecting a parent node to its second and later children with "right"
edges from the 1st child to the 2nd child, 2nd child to third child, etc. Thus at each
step one can either go down to the end) or go right, which shows the correspondence between
the infinite binary tree and the above numbering; the sum of the entries corresponds to the
distance from the root, which agrees with the 2n-1 nodes at depth n-1 in the infinite
binary tree. References
General Dale, Nell. Lilly, Susan D. "Pascal Plus Data
Structures". D. C. Heath and Company. Lexington, MA. 1995. Fourth Edition.
Drozdek, Adam. "Data Structures and Algorithms in C++". Brook/Cole. Pacific Grove, CA. 2001.
Second edition. http:www.math.northwestern.educoursesnotes/dm-treetran
External links Animation Applet of Binary Tree Traversal
The Adjacency List Model for Processing Trees with SQL
Storing Hierarchical Data in a Database with traversal examples in PHP
Managing Hierarchical Data in MySQL Working with Graphs in MySQL
Non-recursive traversal of DOM trees in JavaScript Sample code for recursive and iterative tree
traversal implemented in C. Sample code for recursive tree traversal in
C#. See tree traversal implemented in various
programming language on Rosetta Code Tree traversal without recursion