Repository navigation
Next-pointer and quad tree serializers follow a node that links back to itself #428
Description
#388 gives the binary tree serializers a visited check, but the next-pointer and quad tree serializers walk their children with none, as the review of #388 pointed out. In Org Chart Row Navigation, a linkRowNeighbors that sets root.left = root and leaves root.next null passes the next-pointer check on every level, so the breadth-first walk never ends. In Terrain Mask Tiling, a buildTileTree that returns an internal node whose topLeft is itself makes the preorder walk recurse until the stack runs out. Seven of the ten serializers below then report no case at all, which is the failure #386 reported for binary trees, and the other three blame the stack rather than the tree.
Measured on 3198a99 (macOS 26.5). The page rows come from the interview page in offline mode, the compiled rows from the harness built with cc, g++ and javac and run with a 10 s timeout.
| Serializer | Candidate | What comes back |
|---|---|---|
nextTreeToLevels (web/runners.js) |
root.left = root |
The page shows "Couldn't run your code" and "Execution timed out after 5s - check for an infinite loop." |
_next_tree_to_levels (web/runners.js) |
root.left = root |
The page shows the same timeout message. Run directly under CPython, the walk is still going after 5 s at 884 MB resident. |
C++ nextTreeToJson (web/compiler-explorer.js) |
root->left = root |
Killed by the 10 s timeout, no results. |
Java nextTreeJson (web/compiler-explorer.js) |
root.left = root |
Killed by the 10 s timeout, no results. |
C json_next_tree (web/compiler-explorer.js) |
root->left = root |
SIGSEGV after 0.3 s, no results. #373 adds this refusal to json_next_tree, so this issue leaves it there. |
quadTreeToPreorder (web/runners.js) |
node.topLeft = node |
Every case fails with "Maximum call stack size exceeded". |
_quad_tree_to_preorder (web/runners.js) |
node.topLeft = node |
Every case fails with "RecursionError: maximum recursion depth exceeded". |
C json_quad_tree_visit (web/compiler-explorer.js) |
node->topLeft = node |
SIGSEGV after 589824 bytes of output, no results. |
C++ quadTreeToJson (web/compiler-explorer.js) |
node->topLeft = node |
SIGSEGV, no results. |
Java quadTreeVisit (web/compiler-explorer.js) |
node.topLeft = node |
Every case fails with "java.lang.StackOverflowError". |
Proposed change: the next-pointer serializers refuse a node they reach a second time with "Returned tree must not reach a node twice.", reported as the case's error and keyed on the node rather than its value, as #388 does for binary trees. A correct answer there is the input tree with its next pointers set, so no valid answer reaches a node twice. The quad serializers should refuse only a node that is its own ancestor, tracked along the recursion, because an answer may reuse one leaf for every uniform quarter: a g++ answer that builds one 0 leaf and one 1 leaf and returns them from every uniform region passes all five Terrain Mask Tiling cases on 3198a99, and a visited set would refuse its checkerboard and mixed cases. Since that check can tell a cycle from a shared leaf, its message can say "Returned tree must not contain a cycle." Each serializer gets a self-linked case that fails before the change, plus cases that must keep printing: distinct nodes with equal values in both, and a shared leaf in the quad serializers.
Activity
jserv commentedon Oct 22, 2026
@quill0224 Confirmed on
main(9bc1eae):_next_tree_to_levelsand_quad_tree_to_preorder(web/runners.js:994,:1011) walk children with no visited check, and the same holds for the C++, Java and C quad serializers. Accepted as scoped. The next-pointer serializers refuse a node reached twice with "Returned tree must not reach a node twice.", keyed on identity as #388 does. The quad serializers refuse only a node that is its own ancestor, so shared uniform leaves still pass.json_next_treestays with #373. #417 closes the same gap in the random-list serializers with "Returned list must not reach a node twice."; keep the wording consistent with it. End the PR withCloses #428.