4.3.2.1 - Tree traversals (Python)
Learn to trace pre-order, in-order and post-order traversals, explain where each places the root, and choose an order for copying, sorting output or processing an expression tree.
Pre-order, in-order and post-order
A tree traversal processes every node once, with the root's position distinguishing three important orders.
For these binary-tree traversals, always process the left subtree before the right subtree. “Visit” means perform the required action, such as printing a node's value; moving through a node on the way to its children is not necessarily a visit.
| Traversal | Action order at each node |
|---|---|
| Pre-order | Visit root, traverse left, traverse right |
| In-order | Traverse left, visit root, traverse right |
| Post-order | Traverse left, traverse right, visit root |
Subtree
A node together with all its descendants, treated as a smaller tree with that node as its root.
Use this exact binary tree:
| Node | Left child | Right child |
|---|---|---|
| M | F | T |
| F | B | H |
| T | R | Z |
| B, H, R, Z | none | none |
[DIAGRAM: asset_slug: py_traversal_tree; description: Binary tree rooted at M, with F and T as children, B and H below F, and R and Z below T.]
Pre-order is M, F, B, H, T, R, Z. Complete the entire F subtree before moving to T. In-order is B, F, H, M, R, T, Z. Post-order is B, H, F, R, Z, T, M. The root is first, between its two subtrees, or last respectively; apply this same rule recursively at every node, rather than moving across horizontal rows.
Tracing recursive visits
Recursion handles each subtree with the same rule and returns when it encounters a missing child.
Represent a node as (value, left, right) and a missing child as None. A leaf such as B is ('B', None, None). The base case is a missing node: return without processing anything. At F, in-order first calls B; B's left call returns immediately, B is appended, and its right call returns. Control returns to F, which is appended before the call to H. Only after H completes does the call for F return to M.
Move the visit statement
{"code":"tree = ('M', ('F', ('B', None, None), ('H', None, None)), ('T', ('R', None, None), ('Z', None, None)))\n\ndef inorder(node, result):\n if node is None:\n return\n value, left, right = node\n inorder(left, result)\n result.append(value)\n inorder(right, result)\n\nresult = []\ninorder(tree, result)\nprint(result)","instructions":"Predict the list, then Run. Modify the function by moving result.append(value) before both recursive calls. Predict and Run the resulting pre-order list. Keep the base case first: why does it matter when a child is missing?","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account