# Can Two Binary Search Trees Have the Same Values but Different Structures?

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.

• A 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 Commented Sep 5, 2016 at 17:43

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.

• And 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.

• I'm having a hard time visualizing it. Can you give an example? Commented Sep 5, 2016 at 15:33
• @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) Commented Sep 5, 2016 at 16:03
• That depends on the insertion algorithm obviously. Commented Sep 5, 2016 at 20:53