2

Define a BST as: all left descendants <= n < all right descendants.

Then is it possible to build two binary search trees with different structures but the same exact values? Duplicate values are allowed.

1

2 Answers 2

3

Yes, there can be various BSTs consisting of the same numbers. Let's take the numbers 1, 2, 3.

If the order you add them to the tree is 1, 2, 3 then the tree would have 1 as root, 2 as it's right node and 3 as 2's right node.

If the order is 2, 1, 3 then the tree would have 2 as the root, 1 as the left node and 3 as the right node.

If the order is 3, 1, 2 then the tree would have 3 as the root, 1 as the left node and 2 as the right node of 1. etc.

1
  • 1
    And even with two numbers 1 and 2, you can have either 1 or 2 as the root.
    – gnasher729
    Sep 5, 2016 at 20:52
0

Yes. The structure of the BST Is based on the order jn which the elements are added. So, if you use the same elements, but populate in a different order, you will get a different tree.

3
  • 1
    I'm having a hard time visualizing it. Can you give an example? Sep 5, 2016 at 15:33
  • 1
    @JoshPearce Sure, imagine a tree from (1,2,3). It's either a balanced tree, or a chain. If you have 4 numbers, then you can have 2 different balanced trees with the same values (pick one of the 2 middle elements as the root)
    – Ordous
    Sep 5, 2016 at 16:03
  • That depends on the insertion algorithm obviously.
    – gnasher729
    Sep 5, 2016 at 20:53

Your Answer

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

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