0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Hint: use an inductive strategy. $\endgroup$ – Raphael Dec 11 '15 at 7:50
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.