1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Realz Slaw
    Dec 12, 2012 at 0:54
  • $\begingroup$ I guess you are right. Just find good methods to calculate/extract the size of subtrees. $\endgroup$
    – AJed
    Dec 12, 2012 at 0:56
  • $\begingroup$ @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. $\endgroup$
    – Realz Slaw
    Dec 12, 2012 at 1:20
  • $\begingroup$ Yes. You are right. - I didnt know at the beginning that the question is for full binary trees. $\endgroup$
    – AJed
    Dec 12, 2012 at 3:20

1 Answer 1

2
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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