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!

Binary search tree, number of nodes formula

  1. Sep 19, 2015 #1
    1. The problem statement, all variables and given/known data
    Hello!
    Typical binary search tree has a number of nodes equal to 2^(n+1) - 1.
    I don't understand why we add 1 to the n?
    For example: a tree has a height 4.
    #
    # #
    # # # #
    # # # # # # # #
    each level has 2^i nodes; i = 0, 2^0 = 1 for the first row, etc.
    If the height is 4 then total amount of nodes is 15, which is 2^4 - 1,
    and not 2^(4+1) - 1.

    I would be grateful for your help!
     
  2. jcsd
  3. Sep 19, 2015 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The formula works perfectly well if you regard the depth as n=3, rather than n=4. Four is the number of nodes in a path from root to tip, but three is the number of "steps". It is the same as saying that your first year of life has two endpoints, t = 0 and t = 1, but it is still just one year.
     
  4. Sep 20, 2015 #3
    I see now. Thank you!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted