# Are there any trees where Preorder$(T_1) =$ Preorder$(T_2)$ and Inorder $(T_1) =$Inorder $(T_2)$, but $T_1 \neq T_2$?

Is it possible for two binary trees $$T_1 \neq T_2$$ that both Preorder and Inorder traversal are equal ?

## 1 Answer

Assuming that the nodes in the trees do not have duplicate identities, the inorder and prepoder of the tree together determine the structure of a binary tree. So the answer to your question is: no, that is not possible.

This is relatively simple to see. The preorder "NLR" determines the root "N" of the tree, that is the first node in preorder. Then the nodes left and right of the root, the two subtrees, can be separated using the inorder "LNR": all nodes in inorder before the root go left, all that are after the root go right. Now that we have two sets of nodes, we can recursively proceed for the nodes left and right.