Tree traversals
Not met yet
A traversal visits every card in a tree once, going all the way down the left side before starting on the right. The three usual ones differ only in when a card is written down: before its two sides (pre-order), between them (in-order) or after both (post-order). In-order on a binary search tree gives the numbers sorted. Pre-order puts each card before everything under it, so filing cards in that order rebuilds the same tree. Post-order finishes everything below a card first, like weighing a crate's contents before the crate.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks every traversal of a binary search tree lists the numbers in order, not just the in-order one.
- Thinks a recursive traversal visits a whole level of the tree before the next, rather than going all the way down one side first.
- Thinks post-order is pre-order read backwards, when both still visit the left side before the right.