Convert a post-order binary tree traversal index to an level-order (breadth-first) index
- by strfry
Assuming a complete binary tree, each node can be adressed with the position it appears in a given tree traversal algorithm.
For example, the node indices of a simple complete tree with height 3 would look like this:
breadth first (aka level-order):
0
/ \
1 2
/ \ / \
3 4 5 6
post-order dept first:
6
/ \
2 5
/ \ / \
0 1 3 4
The height of the tree and an index in the post-order traversal is given.
How can i calculate the breadth first index from this information?
