Search code examples
c++algorithmbinary-search-treedepth

Creating a binary search tree with the smallest depth

I have number from 1 to 31 and I need to create a binary search tree with these numbers having the smallest depth. I was thinking of dividing 31/2 and making 16 my root. After that dividing 16/2 and inserting 8 next, but this seems to not work. Is there an algorithm to know in what order to insert the numbers so the tree can have the smallest depth possible?

Solution

  • If you have numbers 1–31, 31 numbers, you want 15 numbers to the left of the root and 15 numbers to the right.
    So the root is 16 (which is not 31/2, but 31/2 + 1).

    Repeating the same procedure, the left subtree has 15 elements, so you want seven numbers on each side of that subtree.
    So the root of the left subtree is 8 (which is 15/2 + 1; there's a pattern here).
    A similar calculation gives the root of the right subtree.

    And so on.