Skip to content

Next-pointer and quad tree serializers follow a node that links back to itself #428

Open

Description

@quill0224

#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

  1. jserv commented on Oct 22, 2026

    @jserv
    Contributor

    @quill0224 Confirmed on main (9bc1eae): _next_tree_to_levels and _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_tree stays 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 with Closes #428.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions