This article is missing citations or needs footnotes. Please help add inline citations to guard against copyright violations and factual inaccuracies. (May 2009)

In computer science, tree-traversal refers to the process of visiting (examining and/or updating) 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.

[edit] Traversal

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 defines 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:

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

(This is also called Depth-first traversal.)

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

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

(This is also called Symmetric traversal.)

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

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

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.

[edit] Example

[edit] 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 sample implementations will require call 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       while node.parent ≠ null and node = node.parent.right         node = node.parent       node = node.parent   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.

[edit] 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) 

[edit] 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 ∗ + 2 3 4, which in infix notation is (2 + 3) ∗ 4, would be evaluated like this:

[edit] 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) 

[edit] 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 using a visited flag:

 nonRecursivePostorder(rootNode)   nodeStack.push(rootNode)   while (! nodeStack.empty())     currNode = nodeStack.peek()     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         nodeStack.pop() 

In this case each node is required to keep an additional "visited" flag, other than usual information (value, left-child-reference, right-child-reference).

Another example is preorder traversal without using a visited flag (Java):

 public void traverseTree(Node root) {    Stack nodes = new Stack();    nodes.push(root);    Node currentNode;    while (! nodes.isEmpty()){       currentNode = nodes.pop();       Node right = currentNode.right();       if (right != null)          nodes.push(right);       Node left = currentNode.left();       if (left != null)          nodes.push(left);             System.out.println("Node data: "+currentNode.data);    } } 

If each node holds reference to the parent node, then iterative traversal is possible without a stack or "visited" flag.

[edit] See also

• Polish notation
• Depth-first search
• Breadth-first search
• Threaded binary tree - linear traversal of binary tree
• Nested set model

[edit] 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

[edit] 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 rosettacode.org