Calculating traversal position of a node in a full binary tree, given its path

Question

Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in the preorder traversal. In other words the $i$th node in the preorder traversal will end up with at this node.

Obviously something better than brute force would be nice.

Answer 1

Essentially the algorithm is:

1. Each time you go left, you add one.
2. 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