CODEWITHSUNDEEP
data-structuresuniquebinary-treebinary-search-tree
Thegluestickman
Thegluestickman

Reputation: 301

Binary Search Tree unique orderings?

Given an arbitrary set of values V and building a tree by inserting values left to right, what does it mean if I'm asked if my orderings of these values (to construct a minimum height and maximum height tree) are unique?

I've read on the internet it must follow a Hamiltonian Path, but we never learned this. And I'm also not quite sure what a Hamiltonian Path is.

Is there a proof that an ordering I choose is a unique ordering?

Upvotes: 0

Views: 145

Answers (1)

templatetypedef
templatetypedef

Reputation: 372704

I believe (though I'm not fully positive) that the question is asking you whether there are multiple different orders into which you could insert the values into the BST that would produce the same tree.

For example, consider this tree:

  1
 / \
0   2

There are two orders in which you could add the values into this tree to produce this result: 1, 0, 2 and 1, 2, 0.

On the other hand, this tree can only be formed in one way:

1
 \
  2

Namely, you have to insert 1 first, then 2.

Hope this helps!

Upvotes: 1

Related Questions