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
-
1A binary search tree can be balanced (or it can be unbalanced). Balancing an unbalanced tree changes the structure while keeping the other natures of the binary search tree. See (algorithm for) keeping a binary search tree balanced– Erik EidtCommented Sep 5, 2016 at 17:43
Add a comment
|
2 Answers
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.
-
1And even with two numbers 1 and 2, you can have either 1 or 2 as the root. Commented Sep 5, 2016 at 20:52
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.
-
1I'm having a hard time visualizing it. Can you give an example? Commented 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)– OrdousCommented Sep 5, 2016 at 16:03
-