Identify balanced and full binary search tree insert order

Question

I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create the binary search tree myself, starting with a root of 8, however I could never get it to be full; the depth would increase from three to four or sometimes five.

How can I come up with an order to insert these numbers into a binary search tree, and get it to be balanced and full?

Answer 1

Keep trying. Try a recursive algorithm. You know that the root needs to be 8. You should be able to infer what numbers need to go in the left subtree of the root. What order should you insert those numbers in, to ensure that the left subtree results in a full and balanced binary tree? Hmm, does that resemble a problem you've seen before? You should be able to take it from there.