New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.
You read a line and hit a footnote marker. Before continuing the sentence, you jump down to read the entire footnote (which may contain its own footnotes). When it's finished, you return and pick up exactly where you left off. Flattening turns that nested reading order into one long, linear transcript — children first, then the rest of the line.
Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.
has a child appended to the flat list
| pop | push next | push child | stack after | flat list so far |
|---|---|---|---|---|
| 1 | 2 | — | [2] | 1 |
| 2 | 3 | 7 | [3, 7] | 1, 2 |
| 7 | 8 | — | [3, 8] | 1, 2, 7 |
| 8 | — | — | [3] | 1, 2, 7, 8 |
| 3 | — | — | [] | 1, 2, 7, 8, 3 |
has a child appended to the flat list
| pop | push next | push child | stack after | flat list so far |
|---|---|---|---|---|
| 1 | 2 | — | [2] | 1 |
| 2 | 3 | 7 | [3, 7] | 1, 2 |
| 7 | 8 | 9 | [3, 8, 9] | 1, 2, 7 |
| 9 | — | — | [3, 8] | 1, 2, 7, 9 |
| 8 | — | — | [3] | 1, 2, 7, 9, 8 |
| 3 | — | — | [] | 1, 2, 7, 9, 8, 3 |
Contrast with Dry run 1: node 7 itself has a child (9). Because a node's child is pushed on top of its next, the deeper branch is always threaded in first — so 9 lands right after 7, before 8. One stack handles any depth; only its height grows.
Both runs step exactly as the tables above. Python pushes curr.next first then curr.child (child ends up on top), and sets curr.child = None after pushing.
Same steps. C++: st.push(curr->next) then st.push(curr->child); set curr->child = nullptr.
Same steps. Java: stack.push(curr.next) then stack.push(curr.child); set curr.child = null.