[xelxebar]

Well the whole point is to use a breadth first order here. I don't think there's a depth vector analogue for breadth first traversals. Is there?

But, indeed, depth vectors are nice and compact. I find them harder to work with most of the time, though, especially since insertions and deletions become O(n), compared to parent vector O(1).

That said, I do often normalize my parent vectors into dfpo order at API boundaries, since a well-defined order makes certain operations, like finding leaf siblings, much nicer.

[ummonk]

I’m not familiar with depth vectors, but wouldn’t the breadth first traversal analogue of each entry specifying its depth (in a depth first format) be each entry specifying the number of immediate children it has?

[dmkolobov]

Yeah, it has its limits for sure. I like it for the streaming aspect.

I think you can still have the functionality described in the article: you would send “hole” markers tagged with their level. Then, you could make additional requests when you encounter these markers during the recovery phase, possibly with buffering of holes. It becomes a sort of hybrid DFS/BFS approach where you send as much tree structure at a time as you want.