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.
-
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 balancedErik Eidt– Erik Eidt2016年09月05日 17:43:06 +00:00Commented Sep 5, 2016 at 17:43
2 Answers 2
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.gnasher729– gnasher7292016年09月05日 20:52:23 +00:00Commented 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?Josh Pearce– Josh Pearce2016年09月05日 15:33:29 +00:00Commented 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– Ordous2016年09月05日 16:03:28 +00:00Commented Sep 5, 2016 at 16:03
-
That depends on the insertion algorithm obviously.gnasher729– gnasher7292016年09月05日 20:53:07 +00:00Commented Sep 5, 2016 at 20:53