calculate Internal path length of a BST only from preorder or postorder traversal

Hello StackOverflow community!

I am trying to figure out how to calculate the internal path length of BST given only the preorder or postorder traversal (it shouldn't make much difference) without constructing the tree; that is, I want to use开发者_运维知识库 only one of traversals mentioned above. This may be a simple answer to most of you, but as you might have already thought I'm quite new at trees.

Well any thought is appreciated and thanks.

Since its a BST we have implicitly have inorder traversal of the tree (sorted list of elements).

We can create a unique tree from just preorder or postorder traversal Pre will be [R, list of elements less then R , list of elements greater then R] Post will be [list of elements less then R , list of elements greater then R, R]

Pseudo code will look like this.

findIPLPreOrder(poArray,startIndex,endIndex, height) {
     if(startIndex==endIndex){
          retrn height;
     }
     m=findIndexOfEndofLeftSubTree(poArray,start,end);
     return findIPLPreOrder(poArray,start+1,m,height + 1) + findIPLPreOrder(poArray,m+1,end,height + 1);     
}

findIndexOfEndofLeftSubTree(poArray,start,end){
  R=poArray[start]
  for(i=start+1;i<=end;i++){
     if(R < poArray[i]){
         return i-1;
       }
  }
}

There is a page at http://geeksforgeeks.org/?p=6633 that discusses building a tree from its preorder and in-order traversals. Here, since your tree is a search tree, you have the in-order traversal implicitly (using the sort order of the keys). You can use a recursive algorithm like the one at that site to compute the level of each tree node (without needing to build the tree), then add the levels together to get the internal path length. That algorithm might not be the most efficient, since it does searches on the traversal to find the right child of each node, but it should work. This is my best guess on how to do a single-pass algorithm (assuming all keys are distinct):

int internal_path_length(key_iter& cur_node, key_iter end, int level, key max_key) {
  if (cur_node == end) return 0;
  key cur_key = *cur_node;
  if (cur_key > max_key) return 0;
  ++cur_node;
  int len1 = internal_path_length(cur_node, end, level + 1, cur_key);
  int len2 = internal_path_length(cur_node, end, level + 1, max_key);
  return len1 + len2 + level;
}

Start with:

key_iter i = preorder.begin();
internal_path_length(i, preorder.end(), 0, mk);

where mk is larger than the largest possible key in your tree.

If I understand your problem it may not be possible. Consider the two trees

   A         A
  / \        |
 B   C       B
             |
             C

These have the same preorder traversal (ABC) but different internal path lengths (2 and 3).