FYI I'm the author of the original I Robot emulator from 1998. This is the one that interprets the mathbox, which means I only know what the mathbox does at the highest 'API' level (can't 100% speak to what the mathbox microcode actually does)

Paul is essentially correct. It's mostly back to front, with some assumptions. I can confirm quite a number of tricks were used, not entirely sure they qualify as a full BSP (although it does involve precompiled mesh optimizations) but then again I'm no BSP expert (just an I Robot expert).

The rasterizer draws a list of polygons (full polys, not just triangles) which must be fully computed before sending to the rasterizer. This "display list" is drawn in order. There is no Z buffer, so everything draws on top of what was already there. So it's important that the display list have the polygons somewhat sorted. Also the polygons are drawn as is, which means rotation/projection is done before being written to the display list.

The camera was fixed (can't yaw) as to simplify math. This means you are always looking straight ahead in Z axis, which allows for all sorts of optimizations. It also makes it trivial to sort objects back to front, simply by checking z coordinate.

Next, the hardware only supports 16 moveable "3D mesh" objects that can be drawn per frame. With an object count this low it's trivial to sort back to front without consuming many CPU cycles. 6809 index instructions make this part a breeze.

The game playfield is "built on the fly", essentially mirroring a 16x16 (16x24? 16x32?) playfield tile array in RAM (each byte encodes tile height), and building each cube face polygon on the fly.

Because of the fixed camera, no real sorting or culling is necessary when creating the display list at the highest level. You simply draw from back of the screen (furthest playfield row) to front (closest row). This process never has to change, it's a linear traversal of playfield array memory, and it always works as long as the camera doesn't yaw. Just draw each row on top of the last one. Guaranteed to not cause problems.

To draw a row (16 tiles, 15 visible) all of the front/top/side polygons are computed and written to the display list. Again, because Z axis is fixed it makes creating the polygon coordinates trivial (you always see front of cube, no culling needed). Once that's done you draw any 3D meshes that are in the row (objects sitting on the playfield cells). Then you move to the next row, and the next, and then you're done.

So at this high level, no real culling is done... things essentially get drawn in order of depth, which always works as long as you don't yaw the camera.

Now... where things get interesting is the 3D mesh objects themselves are stored in a sort of "pre-computed" way to optimize surface removal (not sure if this was done by hand, or by an automated/compile process). It's not so much a tree structure, as it's actually done through specialized instructions. I suppose the jumping/branching is the equivalent of tree traversal.

Basically the meshes are held in ROM, and are really just specialized subroutines, written as a series of simple instructions for the Mathbox. To keep this writeup simple, treat the Mathbox as being able to execute two instructions:

1) write a polygon to the display list
2) "relative jump to instruction" if normal vector dot product points towards/away from camera

A 3D mesh object might be coded in ROM like this

Mathbox3DMeshObject:
if normal vector dot product < 0, jump to X ; pointing away from camera
write poly 1 to display list ; forward facing polygons
write poly 2 to display list
...
Jump to Y
X:
write poly 10 to display list ; back facing polygons
write poly 11 to display list
...
Y:
if normal vector dot product < 0, jump to Z ; sideway facing?
write poly 20 to display list
write poly 21 to display list
...
Z:
write poly 99 to display list ; always drawn
...
END

A mesh object could code any number of jumps, to cover side facing objects, corner cases, etc. Note I'm glossing over the fact that the mathbox would also multiply the coordinates by the current rotation matrix, project to X/Y, perform shading, etc. before emitting to the display list.

As code it's not a real tree structure, although executing the code behaves a lot like traversing a tree. I guess this is sort of a BSP? Can anyone chime in here?

It was pretty clever how it worked out. The mathbox executes the instructions, and creates draw instructions in order. Polygons get skipped by virtue of the fact you're periodically checking normal vectors, and skipping around to different instructions as needed.

Edited: clarity, typos