In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure exactly once. 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.
Types
Unlike linked lists, one-dimensional arrays and other linear data structures, which are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in depth-first or breadth-first order. There are three common ways to traverse them in depth-first order: in-order, pre-order and post-order. Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth-first search. The latter, as well as breadth-first search, can also be used to traverse infinite trees, see below.
Data 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 a stack (LIFO) or queue (FIFO). As a tree is a self-referential (recursively defined) data structure, traversal can be defined by recursion or, more subtly, corecursion, in a natural and clear fashion; in these cases the deferred nodes are stored implicitly in the call stack. Depth-first search is easily implemented via a stack, including recursively (via the call stack), while breadth-first search is easily implemented via a queue, including corecursively.
Depth-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, the following operations are performed 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:
F-B-A-A-A-B-D-C-C-C-D-E-E-E-D-B-F-G-G- I-H-H-H- I- I-G-F
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, the following operations are performed 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 is Monte Carlo tree search, which concentrates on analyzing the most promising moves, basing the expansion of the search tree on random sampling of the search space.
Applications
… excerpt ends here. Continue reading the full article.
