Tree Traversal

From NovaOrdis Knowledge Base
Revision as of 19:50, 10 November 2021 by Ovidiu (talk | contribs) (Created page with "=Internal= * Tree Concepts =Depth First= =Breadth First= =In-Order= '''In-order tree walk''' can be used to print a binary search tree node keys...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Internal

Depth First

Breadth First

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).

Preorder

Postorder