Convert a post-order binary tree traversal index to an level-order (breadth-first) index
Posted
by
strfry
on Stack Overflow
See other posts from Stack Overflow
or by strfry
Published on 2010-12-20T22:47:45Z
Indexed on
2010/12/21
5:00 UTC
Read the original article
Hit count: 267
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?
© Stack Overflow or respective owner
