2

I was studying this https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/ but could not find a way to construct a binary tree using preorder and inorder with duplicate values because hashmaps and linear search does not work in some cases to find the right index. Please tell if there is an algorithm for this. Any kind of help would be appreciated.

Improve this question
3
  • 1
    Probably you can add to a set that tracks already seen indices in case of duplicate values. Commented Jun 23, 2021 at 22:51
  • 3
    If all the values are the same, then the inorder and preorder traversals are the same no matter what the shape of the tree is, so the shape cannot be reconstructed. Commented Jun 24, 2021 at 2:49
  • @MattTimmermans I feel bad but you are right. Its not possible. Commented Jun 24, 2021 at 5:25

2 Answers 2

Reset to default
4

Actually, we can't create a tree from inorder and preorder or inorder and postorder if the tree contains duplicate values.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

If a tree contains duplicates, its inorder and preorder will have multiple repeating elements.

And lets say you follow linear search, you will get one of the all possible trees.

So, such a preorder/postorder and inorder is not able to construct a "unique" binary tree.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.