Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Realz Slaw Dec 12 '12 at 0:54
    
I guess you are right. Just find good methods to calculate/extract the size of subtrees. –  AJed Dec 12 '12 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. –  Realz Slaw Dec 12 '12 at 1:20
    
Yes. You are right. - I didnt know at the beginning that the question is for full binary trees. –  AJed Dec 12 '12 at 3:20
add comment

1 Answer 1

up vote 1 down vote accepted

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
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.