- #1

s3a

- 818

- 8

## Homework Statement

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?

## Homework Equations

Binary search tree algorithm.

## The Attempt at a Solution

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.

Any help would be greatly appreciated!

Thanks in advance!