Walking a Tree
To process every node you need a traversal. For a binary tree there are three depth-first orders, named by when you visit the node itself:
- In-order: left, node, right. On a BST this visits values in sorted order.
- Pre-order: node, left, right. Useful for copying a tree.
- Post-order: left, right, node. Useful for deleting a tree.
There is also level-order (breadth-first): visit the root, then its children, then their children, level by level, using a queue.
Examplepython
Quick check
In-order traversal of a binary search tree gives the values...
Your turn: write the code
Write postorder(n) that returns the values left, right, then node, as a list. Print it for the tree.
Finish the quick check (and any code exercise) to complete this lesson, or mark it done yourself.
Tip: use the left and right arrow keys to move between lessons.