Constructing a Binary Tree from Inorder and Preorder Traversals

Question

I have the following sequences:

Inorder: {4, 2, 5, 1, 6, 3} Preorder: {1, 2, 4, 5, 3, 6}

I'd like to understand how to construct a binary tree from these sequences and why it's possible with this combination of inorder and preorder but not with some other combinations. Additionally, I'm interested in knowing how to implement an algorithm to achieve this in C++.

Here are my specific questions:

How do I construct a binary tree from the given Inorder and Preorder sequences like {4, 2, 5, 1, 6, 3} and {1, 2, 4, 5, 3, 6}? Why is it possible to construct a tree using the Inorder + Preorder or Inorder + Postorder combinations, but not with Preorder + Postorder? Could someone provide a detailed algorithm and code implementation in C++ for constructing the binary tree using Inorder and Preorder traversals? I appreciate any insights and explanations regarding this. Thank you!

   if (traversal_type == "pre") {
        root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start + 1, t_start + left_len, orderIndex, traversal_type);
        root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start + left_len + 1, t_end, orderIndex, traversal_type);
    }
    else if (traversal_type == "post") {
        root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start, t_end - 1, orderIndex, traversal_type);
        root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start, t_start + left_len - 1, orderIndex, traversal_type);
    }

Answer 1

Restating the definitions of the traversals for easy reference. For a given tree with root R and subtrees T_L and T_r, you have:

• pre-order traversal is of the form R T_l... T_r...
• in-order traversal is of the form T_l... R T_r...

If you look at your pre-order traversal, you see the root is 1 but you do not know where T_l stops and T_r starts. Either could be empty. This is where the in-order traversal comes in: everything to the left of 1 is part of T_l and everything to the right is part of T_r. Since 1 is on position 4 of the in-order traversal, the T_l contains 3 items and T_r contains 2 items.

You can now take slices of the input arrays and apply this procedure recursively until you end up with slices of length 1 (leaf node) or 0 (empty subtree).

For a post-order traversal you start reading roots from the end of the array but otherwise nothing changes.

Implementation is left to you, the reader.