Tree traversal
lastmod 2024-07-05created 2020-09-203 edits
In computer science, tree traversal is the process of visiting each node in a tree structure exactly once, in a systematic way. Traversals are classified by the order in which nodes are visited. The algorithms described here are written for binary trees, but they can be generalized to all other trees.
Methods
Linear data structures such as a linked list and a one-dimensional array have only one logical way to traverse, but trees can be traversed in many ways. Starting from the root node of a binary tree, traversal proceeds through three main steps: visiting the current node, traversing the left child node, and traversing the right child node. This process is easily described with recursion.
Data structures for tree traversal
Traversing a tree requires iterating over all nodes in some way.
Because a given node has more than one possible next node (it is not a linear data structure), assuming sequential computation (not parallel), some nodes must be deferred, that is, stored in some way to be visited later. This is often done with a stack (LIFO) or a queue (FIFO).
- Depth-first search is easily implemented with a stack.
- Breadth-first search is easily implemented with a queue.
Preorder traversal
Preorder traversal proceeds as follows.
- Visit the node.
- Traverse the left subtree in preorder.
- Traverse the right subtree in preorder.
Preorder traversal is also called depth-first search.
Inorder traversal
Inorder traversal proceeds in the following order.
- Traverse the left subtree in inorder.
- Visit the node.
- Traverse the right subtree in inorder.
Inorder traversal is also called symmetric traversal.
Postorder traversal
Postorder traversal proceeds as follows.
- Traverse the left subtree in postorder.
- Traverse the right subtree in postorder.
- Visit the node.
Level-order traversal
Level-order traversal visits all nodes in order, starting from the lowest level.
Level-order traversal is also called breadth-first search.