- Binary Tree Puzzle - Draw tree from these traversals: -

inorder: s e u y q r p d f k l m

preorder: f s q y e u p r d k l m

i'm pretty confused middle part. no combination seems work, help? have tricks? how approach this? i've been smacking head on 2 hours.

i must restore tree.

the correct result is

i try provide general explanation instead of concrete 1 example. think more useful , after test algorithm concrete case, see algorithm works , understand better.

you think problem in recursive way.

in order facilitate problem, agree on variables

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

in concrete example, first instance l_p = l_i = 0 , r_p = r_i = 12.

this facilitate explanation:

index     0 1 2 3 4 5 6 7 8 9 10 11 12 preorder: f s q y e u p r d  k  l  m inorder:  s e u y q r p d f  k  l  m           <      left     > ^   < right >                             |                       root 

a important fact realize root of current tree preorder[l_p], first time f. now, must identify left , right branches of tree, distinguished in inorder array (see diagram above). in order know that, search in inorder array index containing root f; index 9. can see root @ 9 places after l_i. let i variable says how many positions respect l_i root of tree.

so, keys of left tree in inorder array between 0 , 8, , keys of right tree between 10 , 12.

in order recursively build left tree have l_p = l_p + 1, because have seen root, , r_ p = l_p + =, array inorder delimited l_i = 0 , r_i = l_i + - 1 =8.

in same way, right tree in preorder between l_p = l_p + + 1 = 10 , r_p = r_p = 12, while in array inorder between l_i = l_i + + 1 , r_i.

with (a little complicated) sketch out 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 = 0; // search index of preorder[l_p] in inorder array   (int j = l_i; j <= r_i; ++j)     if (inorder[j] == preorder[l_p])       {         = j - l_i; // root @ l_i +         break; // breaks if 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 + + 1, r_p,                             inorder, l_i + + 1, r_i);   return root; }