w-16-tree-traversal-animator.yml · YAML
YAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAMLYAML
# Tree traversal animator: chapter widget for 6.1 (panel-a) and 6.3 (panel-b).
# Dual-panel shared widget: same canonical tree, two control-flow shapes.
# Panel-a animates DFS pre/in/postorder with a recursion-stack overlay.
# Panel-b (6.3, scaffolded) animates BFS level-order with a queue overlay.
id: w-16-tree-traversal-animator
title: "Tree traversal animator (DFS pre/in/post + BFS level-order)"
type: dual-panel-shared
level: 1
modes: [preset, edit]
caps:
tree_node_count: { min: 1, max: 8 }
values: { min: -99, max: 99 }
total_steps: { max: 30 }
commands:
- name: render-tree
payload: { tree_repr: 'string' }
description: "Render the binary tree shape; no traversal state yet."
- name: phase-start
payload: { expected_output: 'array' }
description: "Mark the beginning of a traversal phase (preorder | inorder | postorder | level-order | naive-comparison)."
- name: visit
payload: { node: 'string', stack_depth: 'integer', output_after: 'array' }
description: "Highlight the node, append its value to the output ribbon, update the stack-depth column."
- name: enqueue
payload: { node: 'string' }
description: "Append the named node onto the BFS queue. The state.queue field carries the cumulative FIFO contents."
- name: snapshot
payload: { level_size: 'integer' }
description: "BFS only: capture level_size = len(queue) for the next inner loop iteration; render the level-boundary bar."
- name: level-end
payload: { level_index: 'integer', level_values: 'array' }
description: "BFS only: close out the current level; result.append(level); the level-boundary bar drops back to null."
- name: phase-done
payload: { output: 'array' }
description: "Hold the completed-phase frame for emphasis before the next phase starts."
static_fallback:
generator: jsdom
output: site/static/widgets/w-16-tree-traversal-animator-fallback.svg
keyframes_used: [0, "phase-done:preorder", "phase-done:inorder", "phase-done:postorder"]
panels:
panel-a:
chapter: "6.1"
label: "DFS pre / in / postorder on the canonical tree (LC 94 / 144 / 145)"
canonical_input: |
tree = [1, 2, 3, 4, 5, null, 6]
# Shape:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
presets:
- id: lc94_canonical
label: "LC 94 canonical (n=6 tree, all three orderings)"
input:
tree: "[1,2,3,4,5,null,6]"
phases: [preorder, inorder, postorder]
n_steps: 25
keyframes:
- step: 0
kind: render-tree
payload: { tree_repr: "[1,2,3,4,5,null,6]" }
state: { phase: "init", current: null, output: [] }
narration: "Initial tree. Preorder, inorder, and postorder will play in sequence on this same tree. The recursion-stack column is empty."
- step: 1
kind: phase-start
payload: { phase: "preorder", expected_output: [1, 2, 4, 5, 3, 6] }
state: { phase: "preorder", current: null, output: [] }
narration: "Preorder phase. Root visited first, then left subtree, then right. Expected output: [1, 2, 4, 5, 3, 6]."
- step: 2
kind: visit
payload: { node: "node-1", stack_depth: 1 }
state: { phase: "preorder", current: "node-1", output_after: [1] }
narration: "Visit node 1 (root). Output: [1]. Stack depth 1."
- step: 3
kind: visit
payload: { node: "node-2", stack_depth: 2 }
state: { phase: "preorder", current: "node-2", output_after: [1, 2] }
narration: "Recurse into left subtree. Visit node 2. Output: [1, 2]."
- step: 4
kind: visit
payload: { node: "node-4", stack_depth: 3 }
state: { phase: "preorder", current: "node-4", output_after: [1, 2, 4] }
narration: "Recurse left from 2. Visit node 4 (leaf). Output: [1, 2, 4]."
- step: 5
kind: visit
payload: { node: "node-5", stack_depth: 3 }
state: { phase: "preorder", current: "node-5", output_after: [1, 2, 4, 5] }
narration: "Pop back to 2; recurse right. Visit node 5 (leaf). Output: [1, 2, 4, 5]."
- step: 6
kind: visit
payload: { node: "node-3", stack_depth: 2 }
state: { phase: "preorder", current: "node-3", output_after: [1, 2, 4, 5, 3] }
narration: "Pop back to 1; recurse right. Visit node 3. Output: [1, 2, 4, 5, 3]."
- step: 7
kind: visit
payload: { node: "node-6", stack_depth: 3 }
state: { phase: "preorder", current: "node-6", output_after: [1, 2, 4, 5, 3, 6] }
narration: "Recurse right from 3 (left is null). Visit node 6 (leaf). Output: [1, 2, 4, 5, 3, 6]."
- step: 8
kind: phase-done
payload: { output: [1, 2, 4, 5, 3, 6] }
state: { phase: "preorder", output: [1, 2, 4, 5, 3, 6], done: true }
narration: "Preorder complete. Output: [1, 2, 4, 5, 3, 6]."
- step: 9
kind: phase-start
payload: { phase: "inorder", expected_output: [4, 2, 5, 1, 3, 6] }
state: { phase: "inorder", current: null, output: [] }
narration: "Inorder phase. Left subtree, then root, then right. Expected: [4, 2, 5, 1, 3, 6]."
- step: 10
kind: visit
payload: { node: "node-4", stack_depth: 3 }
state: { phase: "inorder", current: "node-4", output_after: [4] }
narration: "Descend left chain to leaf 4 (1 -> 2 -> 4). Visit node 4 first. Output: [4]."
- step: 11
kind: visit
payload: { node: "node-2", stack_depth: 2 }
state: { phase: "inorder", current: "node-2", output_after: [4, 2] }
narration: "Pop to 2; visit it now (left subtree done). Output: [4, 2]."
- step: 12
kind: visit
payload: { node: "node-5", stack_depth: 3 }
state: { phase: "inorder", current: "node-5", output_after: [4, 2, 5] }
narration: "Recurse right from 2 to leaf 5. Visit node 5. Output: [4, 2, 5]."
- step: 13
kind: visit
payload: { node: "node-1", stack_depth: 1 }
state: { phase: "inorder", current: "node-1", output_after: [4, 2, 5, 1] }
narration: "Pop to 1; visit it now (entire left subtree of 1 is done). Output: [4, 2, 5, 1]."
- step: 14
kind: visit
payload: { node: "node-3", stack_depth: 2 }
state: { phase: "inorder", current: "node-3", output_after: [4, 2, 5, 1, 3] }
narration: "Recurse right from 1 to 3. Visit node 3 (left is null). Output: [4, 2, 5, 1, 3]."
- step: 15
kind: visit
payload: { node: "node-6", stack_depth: 3 }
state: { phase: "inorder", current: "node-6", output_after: [4, 2, 5, 1, 3, 6] }
narration: "Recurse right from 3 to leaf 6. Visit node 6. Output: [4, 2, 5, 1, 3, 6]."
- step: 16
kind: phase-done
payload: { output: [4, 2, 5, 1, 3, 6] }
state: { phase: "inorder", output: [4, 2, 5, 1, 3, 6], done: true }
narration: "Inorder complete. Output: [4, 2, 5, 1, 3, 6]."
- step: 17
kind: phase-start
payload: { phase: "postorder", expected_output: [4, 5, 2, 6, 3, 1] }
state: { phase: "postorder", current: null, output: [] }
narration: "Postorder phase. Both subtrees, then root. Expected: [4, 5, 2, 6, 3, 1]."
- step: 18
kind: visit
payload: { node: "node-4", stack_depth: 3 }
state: { phase: "postorder", current: "node-4", output_after: [4] }
narration: "Descend to leaf 4. Visit node 4 first. Output: [4]."
- step: 19
kind: visit
payload: { node: "node-5", stack_depth: 3 }
state: { phase: "postorder", current: "node-5", output_after: [4, 5] }
narration: "Pop to 2, recurse right. Visit node 5 (leaf). Output: [4, 5]."
- step: 20
kind: visit
payload: { node: "node-2", stack_depth: 2 }
state: { phase: "postorder", current: "node-2", output_after: [4, 5, 2] }
narration: "Both subtrees of 2 done. Visit node 2. Output: [4, 5, 2]."
- step: 21
kind: visit
payload: { node: "node-6", stack_depth: 3 }
state: { phase: "postorder", current: "node-6", output_after: [4, 5, 2, 6] }
narration: "Pop to 1, recurse right to 3, recurse right to 6. Visit node 6 (leaf). Output: [4, 5, 2, 6]."
- step: 22
kind: visit
payload: { node: "node-3", stack_depth: 2 }
state: { phase: "postorder", current: "node-3", output_after: [4, 5, 2, 6, 3] }
narration: "Both subtrees of 3 done (left was null). Visit node 3. Output: [4, 5, 2, 6, 3]."
- step: 23
kind: visit
payload: { node: "node-1", stack_depth: 1 }
state: { phase: "postorder", current: "node-1", output_after: [4, 5, 2, 6, 3, 1] }
narration: "Both subtrees of root done. Visit node 1 last. Output: [4, 5, 2, 6, 3, 1]."
- step: 24
kind: phase-done
payload: { output: [4, 5, 2, 6, 3, 1] }
state: { phase: "postorder", output: [4, 5, 2, 6, 3, 1], done: true }
narration: "Postorder complete. Output: [4, 5, 2, 6, 3, 1]. Three orderings, three answers, one tree."
panel-b:
chapter: "6.3"
label: "BFS level-order with queue and level-snapshot (LC 102)"
canonical_input: |
tree = [3, 9, 20, null, null, 15, 7]
# Shape (the canonical LC 102 example):
# 3
# / \
# 9 20
# / \
# 15 7
# Level boundaries: [3] | [9, 20] | [15, 7]
presets:
- id: lc102_canonical
label: "LC 102 canonical (n=5 tree, three levels)"
input:
tree: "[3,9,20,null,null,15,7]"
n_steps: 23
# Trace generated by running the verified §2 Python reference
# (level_order on tree [3, 9, 20, null, null, 15, 7]).
# Visual focus: the FIFO queue evolving cell by cell, the
# `level_size = len(queue)` snapshot bar that appears once per level,
# and the result-of-lists accumulator stacking [[3]] -> [[3], [9, 20]] ->
# [[3], [9, 20], [15, 7]].
keyframes:
- step: 0
kind: render-tree
payload: { tree_repr: "[3,9,20,null,null,15,7]" }
state: { phase: "init", current: null, queue: [], result: [], level: [], level_size: null, output: [] }
narration: "Initial tree. The queue is empty; the result-of-lists accumulator is empty. We will dequeue every node exactly once, grouped by depth."
- step: 1
kind: phase-start
payload: { phase: "level-order", expected_output: [[3], [9, 20], [15, 7]] }
state: { phase: "level-order", current: null, queue: [3], result: [], level: [], level_size: null, output: [] }
narration: "Phase begins. queue = [3]: the root is the only initial pending node."
- step: 2
kind: snapshot
payload: { level_size: 1 }
state: { phase: "level-order", current: null, queue: [3], result: [], level: [], level_size: 1, output: [] }
narration: "Outer iteration 1. level_size = len(queue) = 1. The snapshot pins the level boundary; children appended during this iteration belong to the next level."
- step: 3
kind: visit
payload: { node: "node-3", stack_depth: 1 }
state: { phase: "level-order", current: "node-3", queue: [], result: [], level: [3], level_size: 1, output_after: [3] }
narration: "Inner i=0: dequeue node 3; level = [3]. queue empties momentarily."
- step: 4
kind: enqueue
payload: { node: "node-9" }
state: { phase: "level-order", current: "node-3", queue: [9], result: [], level: [3], level_size: 1, output_after: [3] }
narration: "Append left child: queue = [9]. The 9 sits behind the level-1 boundary; it belongs to level 2."
- step: 5
kind: enqueue
payload: { node: "node-20" }
state: { phase: "level-order", current: "node-3", queue: [9, 20], result: [], level: [3], level_size: 1, output_after: [3] }
narration: "Append right child: queue = [9, 20]. Inner loop has consumed level_size = 1 nodes; ready to close level 0."
- step: 6
kind: level-end
payload: { level_index: 0, level_values: [3] }
state: { phase: "level-order", current: null, queue: [9, 20], result: [[3]], level: [], level_size: null, output: [[3]] }
narration: "End of level 0: result.append(level) → result = [[3]]. Level reset; level_size cleared. Outer loop guard `while queue` re-checks; queue is non-empty."
- step: 7
kind: snapshot
payload: { level_size: 2 }
state: { phase: "level-order", current: null, queue: [9, 20], result: [[3]], level: [], level_size: 2, output: [[3]] }
narration: "Outer iteration 2. level_size = len(queue) = 2. The boundary bar holds: the next two pops belong to level 1."
- step: 8
kind: visit
payload: { node: "node-9", stack_depth: 2 }
state: { phase: "level-order", current: "node-9", queue: [20], result: [[3]], level: [9], level_size: 2, output_after: [9] }
narration: "Inner i=0: dequeue node 9; level = [9]. Node 9 is a leaf; nothing to enqueue."
- step: 9
kind: visit
payload: { node: "node-20", stack_depth: 2 }
state: { phase: "level-order", current: "node-20", queue: [], result: [[3]], level: [9, 20], level_size: 2, output_after: [9, 20] }
narration: "Inner i=1: dequeue node 20; level = [9, 20]. queue is now empty; we'll refill from 20's children."
- step: 10
kind: enqueue
payload: { node: "node-15" }
state: { phase: "level-order", current: "node-20", queue: [15], result: [[3]], level: [9, 20], level_size: 2, output_after: [9, 20] }
narration: "Append 20's left child: queue = [15]. 15 belongs to level 2 (behind the boundary)."
- step: 11
kind: enqueue
payload: { node: "node-7" }
state: { phase: "level-order", current: "node-20", queue: [15, 7], result: [[3]], level: [9, 20], level_size: 2, output_after: [9, 20] }
narration: "Append 20's right child: queue = [15, 7]. Inner loop has consumed level_size = 2 nodes; ready to close level 1."
- step: 12
kind: level-end
payload: { level_index: 1, level_values: [9, 20] }
state: { phase: "level-order", current: null, queue: [15, 7], result: [[3], [9, 20]], level: [], level_size: null, output: [[3], [9, 20]] }
narration: "End of level 1: result.append(level) → result = [[3], [9, 20]]. The boundary held: 9 and 20 grouped, 15 and 7 still pending."
- step: 13
kind: snapshot
payload: { level_size: 2 }
state: { phase: "level-order", current: null, queue: [15, 7], result: [[3], [9, 20]], level: [], level_size: 2, output: [[3], [9, 20]] }
narration: "Outer iteration 3. level_size = 2. The two leaves remain."
- step: 14
kind: visit
payload: { node: "node-15", stack_depth: 3 }
state: { phase: "level-order", current: "node-15", queue: [7], result: [[3], [9, 20]], level: [15], level_size: 2, output_after: [15] }
narration: "Inner i=0: dequeue node 15; level = [15]. Leaf: nothing to enqueue."
- step: 15
kind: visit
payload: { node: "node-7", stack_depth: 3 }
state: { phase: "level-order", current: "node-7", queue: [], result: [[3], [9, 20]], level: [15, 7], level_size: 2, output_after: [15, 7] }
narration: "Inner i=1: dequeue node 7; level = [15, 7]. Leaf. queue is now permanently empty."
- step: 16
kind: level-end
payload: { level_index: 2, level_values: [15, 7] }
state: { phase: "level-order", current: null, queue: [], result: [[3], [9, 20], [15, 7]], level: [], level_size: null, output: [[3], [9, 20], [15, 7]] }
narration: "End of level 2: result.append(level) → result = [[3], [9, 20], [15, 7]]. The boundary held all the way down."
- step: 17
kind: phase-done
payload: { output: [[3], [9, 20], [15, 7]] }
state: { phase: "level-order", current: null, queue: [], result: [[3], [9, 20], [15, 7]], level: [], level_size: null, output: [[3], [9, 20], [15, 7]], done: true }
narration: "Outer loop exits: while queue is False. Return [[3], [9, 20], [15, 7]]: three levels, three lists, boundary preserved."
- step: 18
kind: phase-start
payload: { phase: "naive-comparison", expected_output: [3, 9, 20, 15, 7] }
state: { phase: "naive-comparison", current: null, queue: [3], result: [], level: [], level_size: null, output: [] }
narration: "Compare to the boundary-less naive BFS: same FIFO, no snapshot. queue = [3]; result is a flat list now."
- step: 19
kind: visit
payload: { node: "node-3", stack_depth: 1 }
state: { phase: "naive-comparison", current: "node-3", queue: [9, 20], result: [3], level: [], level_size: null, output_after: [3] }
narration: "Pop 3, append to flat result, enqueue 9 and 20. result = [3]."
- step: 20
kind: visit
payload: { node: "node-9", stack_depth: 2 }
state: { phase: "naive-comparison", current: "node-9", queue: [20], result: [3, 9], level: [], level_size: null, output_after: [3, 9] }
narration: "Pop 9. result = [3, 9]. No children to add."
- step: 21
kind: visit
payload: { node: "node-20", stack_depth: 2 }
state: { phase: "naive-comparison", current: "node-20", queue: [15, 7], result: [3, 9, 20], level: [], level_size: null, output_after: [3, 9, 20] }
narration: "Pop 20. Enqueue 15 and 7. result = [3, 9, 20]. The level boundary that the snapshot version preserved has dissolved: 9, 20, 15, 7 are now intermixed in the same FIFO with nothing distinguishing them by depth."
- step: 22
kind: phase-done
payload: { output: [3, 9, 20, 15, 7] }
state: { phase: "naive-comparison", current: null, queue: [], result: [3, 9, 20, 15, 7], level: [], level_size: null, output: [3, 9, 20, 15, 7], done: true }
narration: "Naive BFS returns the flat [3, 9, 20, 15, 7]. Visit order is right; level grouping is gone. The single line `level_size = len(queue)` is what brought it back."
selector_default: panel-a
notes: |
Dual-panel shared widget. Panel-a (chapter 6.1) animates DFS pre/in/postorder
on the canonical n=6 tree [1,2,3,4,5,null,6] in 25 steps total: one
render-tree + three phases of (phase-start + 6 visits + phase-done) = 1 + 24
= 25, well under the 30-step cap. The recursion-stack column is driven by
stack_depth on each visit command; the AlgoStep auto-inverse handles
rewind on every depth change. Wong palette: orange for the currently-visiting
node, sky blue for visited nodes (during the current phase), bluish green
for the completed-phase output ribbon, blue for unvisited nodes.
Panel-b (chapter 6.3) is scaffolded with the canonical tree and preset
shell only; the keyframe trace for level-order BFS with queue overlay is
authored by the 6.3 research worker. Same canonical tree across both
panels so the reader can scrub DFS in panel-a, then BFS in panel-b, and
visually contrast the two control-flow shapes on identical input.
Trace verification (panel-a): the buffer was generated by running the
verified Python reference ( preorder_recursive /
inorder_recursive / postorder_recursive) on tree [1,2,3,4,5,null,6];
expected outputs ([1,2,4,5,3,6] / [4,2,5,1,3,6] / [4,5,2,6,3,1]) match
the canonical_test cases in chapter frontmatter. Re-running the
generator produces a byte-identical buffer.From The Engineering Handbook (source), CC BY-SA 4.0.