0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.