(redirected from Tree traversal)
Also found in: Dictionary, Thesaurus, Wikipedia.


Processing nodes in a graph one at a time, usually in some specified order. Traversal of a tree is recursively defined to mean visiting the root node and traversing its children. Visiting a node usually involves transforming it in some way or collecting data from it.

In "pre-order traversal", a node is visited __before__ its children. In "post-order" traversal, a node is visited __after__ its children. The more rarely used "in-order" traversal is generally applicable only to binary trees, and is where you visit first a node's left child, then the node itself, and then its right child.

For the binary tree:

T / I S / D E

A pre-order traversal visits the nodes in the order T I D E S. A post-order traversal visits them in the order D E I S T. An in-order traversal visits them in the order D I E T S.
This article is provided by FOLDOC - Free Online Dictionary of Computing (


Crossing over. Passing through. See NAT traversal.
Copyright © 1981-2019 by The Computer Language Company Inc. All Rights reserved. THIS DEFINITION IS FOR PERSONAL USE ONLY. All other reproduction is strictly prohibited without permission from the publisher.
References in periodicals archive ?
Encryption was directly based on the binary traversal, the lexicographic algorithm was more suitable for encryption/ decryption system based on binary tree traversal. And the efficiency of getting the binary tree according to the random number would be higher.
Additionally note that, according to the complexity analysis based on the amount of comparisons in a WPE-enabled K-best tree search published in [35], the complexity of an RVD-based tree traversal doubles that of its complex-plane counterpart.
It waits until the data is read by the output circuit and then continues with tree traversal. This approach eliminates the need for temporary storage.
Meghanathan, "Use of Tree Traversal Algorithms for Chain Formation in the PEGASIS Data Gathering Protocol for Wireless Sensor Networks," KSII Transactions on Internet and Information Systems, vol.
Since the members to a_list are added by tree traversal, they are ordered and so the complexity reduces to linear order, i.e.
[v.sub.b])) be an admissible substitution for T, let ([e.sub.1], ..., [e.sub.a]) and ([l.sub.1], ..., [l.sub.b]) be the lists of scheme edges of T and scheme variables occurring in T both listed according to some fixed tree traversal order (lets say DFS).
Most algorithms that traverse tree structures in a top-down manner use some form of depth-first or breadth-first tree traversal. Finding a leaf node containing a query object q in a spatial index can be done in a depth-first manner by recursively descending the tree structure.
A search operation is then performed by a top-down tree traversal.
If the query point is contained in n, you need to do from top to bottom and sub tree traversal search.