Hacker News Reader

Comment by xelxebar | Hacker News Reader

Very cool point, and it applies to any tree data in general.

I like to represent tree data with parent, type, and data vectors along with a string table, so everything else is just small integers.

Sending the string table and type info as upfront headers, we can follow with a stream of parent and data vector chunks, batched N nodes at a time. Tye depth- or breadth-first streaming becomes a choice of ordering on the vectors.

I'm gonna have to play around with this! Might be a general way to get snappier load time UX on network bound applications.

View on HN

You can even alternate between sending table and node chunks! This will effectively allow you to reveal the tree in any order including revealing children before parents as well as representing arbitrary graphs! Could lead to some interesting applications.

Good point! The parent vector rep is what allows arbitrary node order, but chunking the table data off chunks of node IDs is brilliant idea. Cheers!

If you send the tree in preorder traversal order with known depth, you can send the tree without node ids or parent ids! You can just send the level for each node and recover the tree structure with a stack.

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.

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?

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.

... It might be a pursuit worth making a small library for.

Reply on news.ycombinator.com