Types
UnlikeData structures for tree traversal
Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node (it is not a linear data structure), then, assuming sequential computation (not parallel), some nodes must be deferred—stored in some way for later visiting. This is often done via aDepth-first search
In ''depth-first search'' (DFS), the search tree is deepened as much as possible before going to the next sibling. To traverse binary trees with depth-first search, perform the following operations at each node: # If the current node is empty then return. # Execute the following three operations in a certain order: #: N: Visit the current node. #: L: Recursively traverse the current node's left subtree. #: R: Recursively traverse the current node's right subtree. The trace of a traversal is called a sequentialisation of the tree. The traversal trace is a list of each visited node. 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. There are three methods at which position of the traversal relative to the node (in the figure: red, green, or blue) the visit of the node shall take place. The choice of exactly one color determines exactly one visit of a node as described below. Visit at all three colors results in a threefold visit of the same node yielding the “all-order” sequentialisation: :--------------------------Pre-order, NLR
# Visit the current node (in the figure: position red). # Recursively traverse the current node's left subtree. # Recursively traverse the current node's right subtree. The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.Post-order, LRN
# Recursively traverse the current node's left subtree. # Recursively traverse the current node's right subtree. # Visit the current node (in the figure: position blue). Post-order traversal can be useful to get postfix expression of a binary expression tree.In-order, LNR
# Recursively traverse the current node's left subtree. # Visit the current node (in the figure: position green). # Recursively traverse the current node's right subtree. In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ''ascending'' sorted order.Reverse pre-order, NRL
# Visit the current node. # Recursively traverse the current node's right subtree. # Recursively traverse the current node's left subtree.Reverse post-order, RLN
# Recursively traverse the current node's right subtree. # Recursively traverse the current node's left subtree. # Visit the current node.Reverse in-order, RNL
# Recursively traverse the current node's right subtree. # Visit the current node. # Recursively traverse the current node's left subtree. In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, reverse in-order traversal retrieves the keys in ''descending'' sorted order.Arbitrary trees
To traverse arbitrary trees (not necessarily binary trees) with depth-first search, perform the following operations at each node: # If the current node is empty then return. # Visit the current node for pre-order traversal. # For each ''i'' from 1 to the current node's number of subtrees − 1, or from the latter to the former for reverse traversal, do: ## Recursively traverse the current node's ''i''-th subtree. ## Visit the current node for in-order traversal. # Recursively traverse the current node's last subtree. # Visit the current node for post-order traversal. Depending on the problem at hand, pre-order, post-order, and especially one of the number of subtrees − 1 in-order operations may be optional. Also, in practice more than one of pre-order, post-order, and in-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 search
In ''breadth-first search'' (BFS) or ''level-order search'', the search tree is broadened as much as possible before going to the next depth.Other types
There are also tree traversal algorithms that classify as neither depth-first search nor breadth-first search. One such algorithm isApplications
Pre-order traversal can be used to make a prefix expression ( Polish notation) from expression trees: traverse the expression tree pre-orderly. For example, traversing the depicted arithmetic expression in pre-order yields "+ * ''A'' − ''B'' ''C'' + ''D'' ''E''". In prefix notation, there is no need for any parentheses as long as each operator has a fixed number of operands. Preorder traversal is also used to create a copy of the tree. Post-order traversal can generate a postfix representation (Implementations
Depth-first search implementation
Pre-order implementation
Post-order implementation
In-order implementation
Another variant of Pre-order
If the tree is represented by an array (first index is 0), it is possible to calculate the index of the next element: procedure bubbleUp(array, i, leaf) k ← 1 i ← (i - 1)/2 while (leaf + 1) % (k * 2) ≠ k i ← (i - 1)/2 k ← 2 * k return i procedure preorder(array) i ← 0 while i ≠ array.size visit(array if i = size - 1 i ← size else if i < size/2 i ← i * 2 + 1 else leaf ← i - size/2 parent ← bubble_up(array, i, leaf) i ← parent * 2 + 2Advancing to the next or previous node
Thenode
to be started with may have been found in the binary search tree bst
by means of a standard search function, which is shown here in an implementation without parent pointers, i.e. it uses a stack
for holding the ancestor pointers.
procedure search(bst, key)
// returns a (node, stack)
node ← bst.root
stack ← empty stack
while node ≠ null
stack.push(node)
if key = node.key
return (node, stack)
if key < node.key
node ← node.left
else
node ← node.right
return (null, empty stack)
The function inorderNext returns an in-order-neighbor of node
, either the (for dir=1
) or the (for dir=0
), and the updated stack
, so that the binary search tree may be sequentially in-order-traversed and searched in the given direction dir
further on.
procedure inorderNext(node, dir, stack)
newnode ← node.child ir if newnode ≠ null
do
node ← newnode
stack.push(node)
newnode ← node.child -dir until newnode = null
return (node, stack)
// node does not have a dir-child:
do
if stack.isEmpty()
return (null, empty stack)
oldnode ← node
node ← stack.pop() // parent of oldnode
until oldnode ≠ node.child ir // now oldnode = node.child -dir
// i.e. node = ancestor (and predecessor/successor) of original node
return (node, stack)
Note that the function does not use keys, which means that the sequential structure is completely recorded by the binary search tree’s edges. For traversals without change of direction, the ( amortised) average complexity is because a full traversal takes steps for a BST of size 1 step for edge up and 1 for edge down. The worst-case complexity is with as the height of the tree.
All the above implementations require stack space proportional to the height of the tree which is a Morris in-order traversal using threading
A binary tree is threaded by making every left child pointer (that would otherwise be null) point to the in-order predecessor of the node (if it exists) and every right child pointer (that would otherwise be null) point to the in-order successor of the node (if it exists). 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. # We can make only one traversal at a time. # 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 search
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 half the total number of nodes. A more space-efficient approach for this type of traversal can be implemented using an iterative deepening depth-first search. procedure levelorder(node) queue ← empty queue queue.enqueue(node) while not queue.isEmpty() node ← queue.dequeue() visit(node) if node.left ≠ null queue.enqueue(node.left) if node.right ≠ null queue.enqueue(node.right) If the tree is represented by an array (first index is 0), it is sufficient iterating through all elements: procedure levelorder(array) for i from 0 to array.size visit(arrayInfinite trees
While traversal is usually done for trees with a finite number of nodes (and hence finite depth and finite branching factor) it can also be done for infinite trees. This is of particular interest inReferences
Sources
* 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.External links