1. Not finding help here? Sign up for a free 30min 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!

Minimizing height of binary search tree

  1. Mar 9, 2012 #1

    s3a

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Minimizing height of binary search tree
  1. Binary Hypothesis test (Replies: 0)

Loading...