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

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.

• I think its something like, each time you go left, you add one, and each time you go right, you add the size of the left subtree. Dec 12, 2012 at 0:54
• I guess you are right. Just find good methods to calculate/extract the size of subtrees.
– AJed
Dec 12, 2012 at 0:56
• @AJed I think something like $2^{h-l}$, where $h$ is the height of the tree, and $l$ is the level. $l$ can be calculated incrementally along the path. Dec 12, 2012 at 1:20
• Yes. You are right. - I didnt know at the beginning that the question is for full binary trees.
– AJed
Dec 12, 2012 at 3:20

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