Tree Traversal: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
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]]
=Depth First=
=Overview=
=Breadth First=
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 walk''' can be used to print a binary search tree node keys in sorted 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.
<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.

Depth First

Breadth First