3 ms·

An Encoded Tree Traversal

65 points by dmit 8y ago

cat199 8y ago
> 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 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
ball_of_lint 8y ago
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.
- deleted 8y ago
  [deleted]
- mlthoughts2018 8y ago
  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.
- rsc 8y ago
  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.
bra-ket 8y ago
great interview question
- sushisource 8y ago
  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.
- rsc 8y ago
  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.

65 points by dmit 8y ago

> 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 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

ball_of_lint 8y ago

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.

deleted 8y ago
[deleted]
mlthoughts2018 8y ago
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.
rsc 8y ago
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.

bra-ket 8y ago

great interview question

sushisource 8y ago
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.
rsc 8y ago
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.