In computer science, tree traversal is the process of visiting each node in a tree data structure. Tree traversal, also called walking the tree, provides for sequential processing of each node in what is, by nature, a non-sequential data structure. 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.

Traversal methods

Say we have a tree node structure which contains a value value and references left and right to its two children. Then we can write the following function:

visit(node)
    print node.value
    if node.left  != null then visit(node.left)
    if node.right != null then visit(node.right)

This prints the values in the tree in pre-order. In pre-order, each node is visited before any of its children. Similarly, if the print statement were last, each node would be visited after all of its children, and the values would be printed in post-order. In both cases, values in the left subtree are printed before values in the right subtree.

visit(node)
    if node.left  != null then visit(node.left)
    print node.value
    if node.right != null then visit(node.right)

An in-order traversal, as above, visits each node between the nodes in its left subtree and the nodes in its right subtree. This is a particularly common way of traversing a binary search tree, because it gives the values in increasing order.

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.

If instead we visit the right subtree, then the current node, then the left subtree, this produces the opposite order as in-order traversal, sometimes called a reverse in-order or reverse-order traversal.

Examples

In this binary tree, Preorder (NLR) traversal yields: 2, 7, 2, 6, 5, 11, 5, 9, 4 Postorder (LRN) traversal yields: 2, 5, 11, 6, 7, 4, 9, 5, 2 In-order (LNR) traversal yields: 2, 7, 5, 6, 11, 2, 5, 4, 9

Functional traversal

We could perform the same traversals in a functional language like Haskell using code like 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 traversal

All of the above recursive algorithms use stack space proportional to the depth of the tree. If we store on each node a reference to its parent, then we can implement all of these traversals in-place using a simple iterative algorithm. The parent references occupy much more space, however; this is only really useful if the parent references are needed anyway, or stack space in particular is limited. For example, here is an iterative algorithm for in-order traversal:

visit(root) {
    prev    := null
    current := root
    next    := null
   
    while current ≠ null {
        if prev == current.parent
            prev := current
            next := current.left
        if next == null or prev == current.left
            print current.value
            prev := current
            next := current.right
        if next == null or prev == current.right
            prev := current
            next := current.parent
        current := next
    }
}