An Encoded Tree Traversal | Hacker News Reader

An Encoded Tree Traversal

research.swtch.com

65 pointsdmit7 comments

> There must be existing uses of this encoding, but I’ve been unable to find any or even determine what its name is.

not a tree guru.. but isn't this somewhat related to 'fractal tree indexing':

https://en.wikipedia.org/wiki/Fractal_tree_index

    Each internal node of a B-tree will contain a number of keys that is 
    one less than its branching factor. The keys act as separation values 
    which divide its subtrees. Keys in subtrees are stored in search tree order, 
    that is, all keys in a subtree are between the two bracketing values. 
    In this regard, they are just like B-trees.

also, thanks for the plan9 stuff :D

I like using a level-order traversal because it makes your indexing very simple. For a binary tree you start with 1 and each node has children 2 * i and 2 * i + 1, and parent i / 2. You can do a inorder/preorder/postorder traversal using the typical methods, but for a level-order traversal all you need to do is walk through the backing array.

This also generalizes to k-trees. Start at node k-1. your children are ((i - k + 2) * k) through ((i - k + 2) * k) + (k - 1), and your parent is ((i / k) - 2 + k) with integer division. Once again this all fits nicely into a flat backing array and requires no extra memory to store children or parents.

This assumes some type of array-backed tree, rather than a pointer / node implementation. In that case, level order usually requires pushing child nodes onto a queue or something similar, which I personally always find tedious by comparison to simpler traversals.

I agree, this is a great representation - I think of it as the heap ordering - but it assumes a fixed-height tree. For my use case, I want to overlay increasingly large trees (with leaves appended to the right side) to a linear array, so heap order is a non-starter.

great interview question

I disagree completely. This problem will never matter to the day job of 99%+ of engineers. It's fun to read about, fun to think about outside of an interview context, but it's a garbage test of whether or not I'd want to hire someone.

It's a terrible interview question, not least because I spent however long writing 4 pages about it and still don't know what it is. :-)

But it's not made up: this comes up in a real system and I would like to know more about the answer.

Reply on news.ycombinator.com