- Binary Tree Puzzle - Draw tree from these traversals:

Question

Inorder: S A E U Y Q R P D F K L M

Preorder: F A S Q Y E U P R D K L M

I'm pretty confused about what to do with the middle part. No combination seems to work, help? Does anyone have tricks? How do I approach this? I've been smacking my head on this for 2 hours.

I must restore the tree.

Answer 1

The correct result is

I will try to provide you a general explanation instead of a concrete one for your example. I think it is more useful and after all you could test the algorithm with your concrete case, see that the algorithm works and understand better.

You could think the problem in a recursive way.

In order to facilitate the problem, we could agree on some variables

• preorder: an array containing the preorder traversal
• inorder: an array containing the inorder traversal
• l_p: left index in the preorder array
• r_p: right index in the preorder array
• l_i: left index in the inorder array
• r_i: right index in the inorder array

In your concrete example, the first instance would be l_p = l_i = 0 and r_p = r_i = 12.

This could facilitate the explanation:

index     0 1 2 3 4 5 6 7 8 9 10 11 12
preorder: F A S Q Y E U P R D  K  L  M
inorder:  S A E U Y Q R P D F  K  L  M
          <      left     > ^   < right >
                            |
                      this is the root

A very important fact is to realize that the root of current tree is always preorder[l_p], which the first time is F. Now, you must identify the left and right branches of the tree, which are clearly distinguished in the inorder array (see diagram above). In order to know that, you search in the inorder array the index containing the root F; this index is 9. We can see that the root is at nine places after l_i. Let i a variable that says how many positions respect to l_i is the root of the tree.

So, the keys of left tree are in inorder array between 0 and 8, and the keys of the right tree are between 10 and 12.

In order to recursively build the left tree you have l_p = l_p + 1, because you have already seen the root, and r_ p = l_p + i =, but the array inorder is delimited by l_i = 0 and r_i = l_i + i - 1 =8.

In the same way, the right tree is in preorder between l_p = l_p + i + 1 = 10 and r_p = r_p = 12, while in the array inorder it is between l_i = l_i + i + 1 and r_i.

With all this (a little complicated) we could sketch out an algorithm:

Node * build_tree(int preorder[], int l_p, int r_p,
                  int inorder[], int l_i, int r_i)
{
  if (l_p > r_p)
    return nullptr; // empty tree

  Node * root = new Node;
  root->key = preorder[l_p];

  int i = 0; // now we search index of preorder[l_p] in inorder array
  for (int j = l_i; j <= r_i; ++j)
    if (inorder[j] == preorder[l_p])
      {
        i = j - l_i; // the root is at l_i + i
        break; // always breaks if everything is ok
      }

  root->left = build_tree(preorder, l_p + 1, l_p + i, 
                          inorder, l_i, l_i + (i - 1));
  root->right = build_tree(preorder, l_p + i + 1, r_p, 
                           inorder, l_i + i + 1, r_i);
  return root;
}