# Dictionary Definition

traversal

### Noun

1 taking a zigzag path on skis [syn: traverse]

2 travel across [syn: traverse]

# User Contributed Dictionary

## English

### Noun

- The act of traversing; a crossing
- The product or result of traversing

#### Related terms

# Extensive Definition

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.

## Traversal methods

Compared to linear data structures like linked lists and one dimensional arrays, which have only one logical means 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 define the traversal type. These steps (in no particular order) are: performing an action on the current node (referred to as "visiting" the node), traversing to the left child node, and traversing to the right child node. Thus the process is most easily described through recursion.To traverse a non-empty binary tree in preorder,
perform the following operations recursively at each node, starting
with the root node:

- Visit the node.
- Traverse the left subtree.
- Traverse the right subtree.

To traverse a non-empty binary tree in inorder,
perform the following operations recursively at each node, starting
with the root node:

- Traverse the left subtree.
- Visit the node.
- Traverse the right subtree.

To traverse a non-empty binary tree in postorder,
perform the following operations recursively at each node, starting
with the root node:

- Traverse the left subtree.
- Traverse the right subtree.
- Visit the node.

Finally, trees can also be traversed in
level-order, where we visit every node on a level before going to a
lower level. This is also called Breadth-first
traversal.

### Example

### Sample implementations

preorder(node) print node.value if node.left ≠
null then preorder(node.left) if node.right ≠ null then
preorder(node.right)

inorder(node) if node.left ≠ null then
inorder(node.left) print node.value if node.right ≠ null then
inorder(node.right)

postorder(node) if node.left ≠ null then
postorder(node.left) if node.right ≠ null then
postorder(node.right) print node.value

All three recursive sample implementations will
require stack space proportional to the height of the tree. In a
poorly balanced tree, this can be quite considerable.

We can remove the stack requirement by
maintaining parent pointers in each node, or by threading
the tree. In the case of using threads, this will allow for
greatly improved inorder traversal, although retrieving the parent
node required for preorder and postorder traversal will be slower
than a simple stack based algorithm.

To traverse a threaded tree inorder, we could do
something like this:

inorder(node) while hasleftchild(node) do node =
node.left do visit(node) if (hasrightchild(node)) then node =
node.right while hasleftchild(node) do node = node.left else node =
node.right while node ≠ null

Note that a threaded binary tree will provide a
means of determining whether a pointer is a child, or a thread. See
threaded
binary trees for more information.

### Level order traversal

Level order traversal is a traversal method by
which levels are visited successively starting with level 0 (the
root node), and nodes are visited from left to right on each
level.

This is commonly implemented using a queue data
structure with the following steps (and using the tree below as an
example):

Step 1: Push the root node onto the queue (node
2): New queue: 2- - - - - - - - - -

Step 2:

Pop the node off the front of the queue (node
2).

Push that node's left child onto the queue (node
7).

Push that node's right child onto the queue (node
5).

Output that node's value (2).

New queue: 7-5- - - - - - - - - Output: 2

Step 3:

Pop the node off the front of the queue (node
7).

Push that node's left child onto the queue (node
2).

Push that node's right child onto the queue (node
6). Output that node's value (7).

New queue: 5-2-6- - - - - - - - Output: 2 7

Step 4:

Pop the node off the front of the queue (node 5).
Push that node's left child onto the queue (NULL, so take no
action). Push that node's right child onto the queue (node 9).
Output that node's value (5).

New queue: 2-6-9- - - - - - - - Output: 2 7
5

Step 5:

Pop the node off the front of the queue (node
2).

Push that node's left child onto the queue (NULL,
so take no action).

Push that node's right child onto the queue
(NULL, so take no action).

Output that node's value (2).

New queue: 6-9- - - - - - - - - Output: 2 7 5
2

Step 6:

Pop the node off the front of the queue (node
6).

Push that node's left child onto the queue (node
5).

Push that node's right child onto the queue (node
11).

Output that node's value (6).

New queue: 9-5-11- - - - - - - - Output: 2 7 5 2
6

Step 7:

Pop the node off the front of the queue (node
9).

Push that node's left child onto the queue (node
4).

Push that node's right child onto the queue
(NULL, so take no action).

Output that node's value (9).

New queue: 5-11-4- - - - - - - - Output: 2 7 5 2
6 9

Step 8: You will notice that because the
remaining nodes in the queue have no children, nothing else will be
added to the queue, so the nodes will just be popped off and output
consecutively (5, 11, 4). This gives the following:

Final output: 2 7 5 2 6 9 5 11 4

which is a level-order traversal of the
tree.

### Queue-based level order traversal

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 q.enqueue(node.left) if node.right ≠ null
q.enqueue(node.right)

### Uses

Inorder traversal

It is particularly common to use an inorder
traversal on a binary
search tree because this will return values from the underlying
set in order, according to the comparator that set up the binary
search tree (hence the name).

To see why this is the case, note that if n is a
node in a binary search tree, then everything in n 's left subtree
is less than n, and everything in n 's right subtree is greater
than or equal to n. Thus, if we visit the left subtree in order,
using a recursive call, and then visit n, and then visit the right
subtree in order, we have visited the entire subtree rooted at n in
order. We can assume the recursive calls correctly visit the
subtrees in order using the mathematical principle of structural
induction. Traversing in reverse inorder similarly gives the
values in decreasing order.

Preorder traversal

Traversing a tree in preorder while inserting the
values into a new tree is common way of making a complete copy of a
binary
search tree.

One can also use preorder traversals to get a
prefix expression (Polish
notation) from expression
trees: traverse the expression tree preorderly. To calculate
the value of such an expression: scan from right to left, placing
the elements in a stack.
Each time we find an operator, we replace the two top symbols of
the stack with the result of applying the operator to those
elements. For instance, the expression ∗ + 234, which in infix
notation is (2 + 3) ∗ 4, would be evaluated like this:

## Functional traversal

We could perform the same traversals in a functional language like Haskell using code similar to this: data Tree a = Nil | Node (Tree a) a (Tree a) preorder Nil = [] preorder (Node left x right) = [x] ++ (preorder left) ++ (preorder right) postorder Nil = [] postorder (Node left x right) = (postorder left) ++ (postorder right) ++ [x] inorder Nil = [] inorder (Node left x right) = (inorder left) ++ [x] ++ (inorder right)## Iterative traversing

All the above recursive algorithms require stack space proportional to the depth of the tree. Recursive traversal may be converted into an iterative one using various well-known methods.A sample is shown here for postorder
traversal:

nonrecursivepostorder (rootNode) nodeStack.push
(rootNode) while (true) currNode = nodeStack.pop () if
((currNode.left != null) and (currNode.left.visited

## false)) nodeStack.push (currNode.left) else if ((currNode.right != null) and (currNode.right.visited

false)) nodeStack.push (currNode.right) else print currNode.value currNode.visited := true if nodeStack.empty() breakIn this case, for each node is required to keep
an additional "visited" flag, other than usual informations (value,
left-child-reference, right-child-reference).

## See also

- Tree programming
- Polish notation
- Depth-first search
- Breadth-first search
- Threaded binary tree - linear traversal of binary tree

## External links

## References

- 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.edu/~mlerma/courses/cs310-05s/notes/dm-treetran

traversal in Japanese: 木構造 (データ構造)

traversal in Polish: Przechodzenie drzewa

traversal in Vietnamese: Duyệt cây

traversal in Ukrainian: Обхід дерева

traversal in Chinese: 图遍历