Tree Traversal: Difference between revisions
Jump to navigation
Jump to search
m (Ovidiu moved page Tree Walking to Tree Traversal without leaving a redirect) |
No edit summary |
||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Tree_Concepts#Tree_Walking|Tree Concepts]] | * [[Tree_Concepts#Tree_Walking|Tree Concepts]] | ||
=In-Order= | =In-Order= | ||
'''In-order tree walk''' can be used to print a binary search tree node keys in sorted order. | '''In-order tree walk''' can be used to print a binary search tree node keys in sorted order. | ||
| Line 12: | Line 10: | ||
</font> | </font> | ||
The running time is O(n). | The running time is O(n). | ||
=Preorder= | =<span id='Preorder'></span>Pre-Order= | ||
=Postorder= | =<span id='Postorder'></span>Post-Order= | ||
=Depth First= | |||
=Breadth First= | |||
Revision as of 22:27, 10 November 2021
Internal
In-Order
In-order tree walk 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).