Essentially the algorithm is:
- Each time you go left, you add one.
- Each time you go right, you add the size of the left sub-tree, and you add one.
The size of a full binary tree can be calculated as $2^{h+1}-1$. Thus, the height of the left sub-tree can be calculated by $2^{h_{\text {subtree}}+1}-1=2^{h-l+1}-1$ where $l$ is the level of the left sub-tree.
#WARNING: non tested, python-ish
def calc_tree_size(tree_height):
return (1<<(tree_height+1)) - 1
def inorder_traversal_position(tree_height,path):
result = 0
for level in range(len(path)):
if path[level] == 0:
#If we go left,
#Preorder goes left after visiting a node.
#Add one for the node we just visited.
result += 1
elif path[level] == 1:
#If we go right,
#Preorder normally goes left, visiting all the nodes
# in the left sub-tree before going right.
#Add the number of nodes in the left sub-tree.
left_subtree_level = level + 1
left_subtree_height = tree_height - left_subtree_level
left_subtree_size = calc_tree_size(left_subtree_height)
result += left_subtree_size
#Add one for the node we just visited.
result += 1
return result