1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Minimizing height of binary search tree

  1. Mar 9, 2012 #1


    User Avatar

    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations
    Binary search tree algorithm.

    3. 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!
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted