Tree Traversal: Difference between revisions
m (Ovidiu moved page Tree Walking to Tree Traversal without leaving a redirect) |
|||
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Tree_Concepts#Tree_Walking|Tree Concepts]] | * [[Tree_Concepts#Tree_Walking|Tree Concepts]] | ||
= | =Overview= | ||
The traversal style is named relative to the node itself. [[#Preorder|Pre-order]] means the node is traversed (processed first), [[#Postorder|post-order]] means that the node is traversed (processed) last, and[[#In-Order| in-order]] means that the processing is done in order from left to right: left subtree, node, right subtree. | |||
=In-Order= | =In-Order= | ||
'''In-order tree | In-order traversal means to recursively visit the '''left branch, the node itself, and then the right branch''' (in order). In-order tree traversal can be used to print a binary search tree node keys in sorted order. | ||
<font size=-1> | <font size=-1> | ||
let r = root of the search tree with subtrees T<sub>L</sub> and T<sub>R</sub> | let r = root of the search tree with subtrees T<sub>L</sub> and T<sub>R</sub> | ||
| Line 12: | Line 13: | ||
</font> | </font> | ||
The running time is O(n). | The running time is O(n). | ||
=Preorder= | |||
=Postorder= | =<span id='Preorder'></span>Pre-Order= | ||
Pre-order tree traversal means to first visit (process) the current node, then branches, starting with the left branch and continuing with the right branch. | |||
=<span id='Postorder'></span>Post-Order= | |||
Post-order tree traversal means to first visit (process) the branches in the order left, right, then the current node. | |||
=Depth First= | |||
=Breadth First= | |||
Latest revision as of 22:34, 10 November 2021
Internal
Overview
The traversal style is named relative to the node itself. Pre-order means the node is traversed (processed first), post-order means that the node is traversed (processed) last, and in-order means that the processing is done in order from left to right: left subtree, node, right subtree.
In-Order
In-order traversal means to recursively visit the left branch, the node itself, and then the right branch (in order). In-order tree traversal can be used to print a binary search tree node keys in sorted order.
let r = root of the search tree with subtrees TL and TR recurse of TL # by recursion/induction, prints out keys of TL in increasing order print out r's key recurse of TR # by recursion/induction, prints out keys of TR in increasing order
The running time is O(n).
Pre-Order
Pre-order tree traversal means to first visit (process) the current node, then branches, starting with the left branch and continuing with the right branch.
Post-Order
Post-order tree traversal means to first visit (process) the branches in the order left, right, then the current node.