Tree traversal
From Wikipedia, the free encyclopedia
 |
This article or section may require cleanup to meet Wikipedia's quality standards. Please help improve this article or replace this tag with a more specific message. This article has been tagged since July 2006. (help, talk) |
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.
Contents |
[edit] 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:
pre-order (prefix) traversal
This recursive algorithm prints the values in the tree in pre-order. In pre-order, each node is visited before any of its children.
visit(node)
print node.value
if node.left != null then visit(node.left)
if node.right != null then visit(node.right)
post-order (postfix) traversal
Similar to the pre-order is the post order - where each node is visited after all of its children. 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)
if node.right != null then visit(node.right)
print node.value
in-order (infix) traversal
An in-order traversal visits each node after it visits the nodes of its left subtree but before visiting the nodes of its right subtree. This is a particularly common way of traversing a binary search tree, because it gives the values in increasing order.
visit(node)
if node.left != null then visit(node.left)
print node.value
if node.right != null then visit(node.right)
To see why this is the case, note that if n is a node in a binary search tree, then everything in ns left subtree is less than n, and everything in ns 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.
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.
level order traversal
visitlevel(S)
T = Set()
for each node in S
print node.Value
if (node->left != null)
T.insert(node->left)
if (node->right != null)
T.insert(node->right)
if ( T.empty() != true)
visitlevel(T)
visit(root)
S = Set()
S.insert(root)
visitlevel(S)
This prints the nodes in the order of their depth from the root. See the iterative version below.
[edit] Examples
 |
In this binary tree,
D = data, L = left, R = right
|
[edit] 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)
[edit] 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) {
midvisit() {
print current.value
next := current.right
if next == null
next := current.parent
}
prev := null
current := root
while current ≠ null
if prev == current.parent
next := current.left
if next == null
midvisit()
else if prev == current.left
midvisit()
else
next := current.parent
prev := current
current := next
}
A similar scheme using a queue can effect level-order traversal, where we visit the nodes in each level of the tree from left to right. However, the space used is no longer proportional to the tree height but to the maximum tree level size, which can be as large as n/2. A more space-efficient approach for this type of traversal can be implemented using iterative deepening depth-first search.
visit(root) {
q := empty queue
add root to the end of q
while q is not empty {
node := get and remove first element of q
print node.value
if node.left ≠ null
add node.left to the end of q
if node.right ≠ null
add node.right to the end of q
}
}
