Binary Search Tree Confusion (best-case)

Question

I am currently studying for an exam and one of the questions I am confused about is:

Give 5 orderings of the key A X C S E R H that, when inserted into an initiall empty BST, produce the best-case tree. Assume the lexicographical/alphabetical ordering.

The answer to this is provided as:

Here are some possible oderings...

H C A E S R X

H C A E S X R

H C E A S R X

H C E A S X R

H C E S A R X

I was wondering if someone can give me some clarification to how 'H' would take on the root node? From my current understanding I assumed 'A' would be the root. I think I need some clarification on how to get to the best-case tree of a BST. If someone could help me understand this I would greatly appreciate it.

Answer 1

Your first entry will be your root. After that, anything that comes BEFORE your root (alphabetically in this case) will go to the left; AFTER will go to the right.

Each of those produces a tree that can be traced from the bottom left to the bottom right in alphabetical order.

As you can see this produces a tree which can be read bottom left up towards the root (exploring each branch from the parent before continuing upwards) to create an alphabetic sequence