Question

Given a binary search tree that contains n nodes with keys 1, 2, 3, ... , n.

In what order should the keys be inserted into the binary search tree to obtain a tree with minimal height?

Answer 1

I'm assuming height and depth are the same in this case since I read that height is calculated by traversing from a leaf to a node whereas the depth is calculated by traversing from the root to a node. I believe that I must have each branch branch off to another two branches except for the leaves in order to minimize the height/depth. I know how a binary search tree works but given that we are dealing with an infinite amount of nodes, I don't know how to answer the question.

Answer 2

Well, work it out for a concrete example first, say, n=16.

And then generalize, e. g. using k, k+1 etc., or whatever notation makes sense.

Answer 3

height is a property of the tree, depth is how how far ("deep", sorry :-) you go in a search (of a tree).

Answer 4

Damn, I'm having trouble even doing that n = 16 thing. I can only tell if the tree is a binary search tree, that is if each node has their left subnode contain a smaller value and the right node contain a value greater than or equal to its parent node.

Answer 5

Well, try the numbers in sequence, inserting in the correct place for a BST. That will probably not give you the minimum height tree, but perhaps you gain some insight on what you'd need to do to get there.

Just fool around with some attempts to gain some intuition. That may give you an idea, etc....