Tree Traversal: Difference between revisions
Jump to navigation
Jump to search
| Line 2: | Line 2: | ||
* [[Tree_Concepts#Tree_Walking|Tree Concepts]] | * [[Tree_Concepts#Tree_Walking|Tree Concepts]] | ||
=In-Order= | =In-Order= | ||
In-order traversal means to recursively visit the left branch, the node itself, and then the right branch | 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> | ||
Revision as of 22:29, 10 November 2021
Internal
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).