This is task I found from old exam and I try it for solved because they can ask similar question for me on friday.
For solution I have cheap solution but I think it all matter of definition of binary search tree.
I make first tree:
1
\
1
\
1
and here is second tree
1
/
1
/
1
When you make pre order traversal you have same output for both tree.. because same element, and both have degenerated tree. But you don't have same tree! So statement is false.
Only problem is are my tree binary search tree... I think yes because binary search tree the element can have greater / lower equal element?
Please halp when I asked our teacher he say I can ask him when vacation is over but when vacation is over my exam is over.... No good thing for me.
Your answer is perfectly fine given the standard definition of BSTs. By the standard definition, BSTs can have repeated elements and identical elements can go in either subtree.
If the question intends the case where there are no duplicates, or where duplicates must exist in only the left (or only the right) subtree, then a pre-order traversal is sufficient to reconstruct the tree.
If duplicates are not allowed, construct the tree recursively as follows: make the root the first node, and then make the left and right subtrees recursively using as input traversals the portions of the original traversal with nodes less than (for left subtree) and greater than (for right subtree) the root node. If duplicates are allowed but are constrained to either the left or the right subtree, then use the same procedure but adding "or equal" to either the less than or the greater than, but not both.