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)
No edit summary
Line 1: Line 1:
=Internal=
=Internal=
* [[Tree_Concepts#Tree_Walking|Tree Concepts]]
* [[Tree_Concepts#Tree_Walking|Tree Concepts]]
=Depth First=
=Breadth First=
=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).

Pre-Order

Post-Order

Depth First

Breadth First