Link to home
Start Free TrialLog in
Avatar of pzozulka
pzozulka

asked on

Binary Search Tree: How many trees of height 3 possible with 5 nodes

A BST is generated from each permutation of keys from the set {1, 2, 3, 4, 5}.
How many different-looking trees of height two are produced?
How many different-looking trees of height three are produced?

With the help of link below, I now know how to calculate how many distinct trees are possible for any number of nodes. In this case, 5 nodes, there are 42 possible distinct trees. http://gatecse.in/wiki/Number_of_Binary_trees_possible_with_n_nodes

However, how do I calculate the number of trees when you are limited to a height of two or three or whatever number?
Avatar of d-glitch
d-glitch
Flag of United States of America image

For depth =  3:
The root at d=0 can have L or R child on d=1.
The child at d=1 can have L or R child on d=2.
The child at d=2 can have L or R child on d=3.

There are three binary choices for eight possibilities and you have used up four elements.
The last element can go to any of the three available positions on d=1, 2, or 3.

So there are 3 x 8 = 24 trees of height/depth equal to 3
For depth =  2:
The root at d=0 must have L and R children on d=1.

You have used up three elements.  The other two elements must go on d=2.
L and R on L1.
L and R on R1.
L on L1 and L on R1.
L on L1 and R on R1.
R on L1 and L on R1.

So there are 6 trees of height/depth equal to 2
Avatar of pzozulka
pzozulka

ASKER

I can't imagine having to count all the possibilities if I was given 12 elements for example, and asked to find the amount of trees for larger amount of levels, like 5 for example. Is there no formula to calculate this?
This is essentially a combinatorics problem, which can be very difficult.

For depth=5 with twelve elements:
There are 2^5 = 32 ways to make a chain from the root to the required depth using six elements.
You still have six elements to place, and things get tricky fast.
There is room for more 1 element under the d=4 node, 3 under the d=3, 7 under the d=2, and 15 under the d=1.

There are lots of ways to count the number (build the tree recursively), but I don't see a way to calculate it.
I will keep thinking.
For depth=5 with 12 elements, I got 23,608. Is that right?
>> For depth=5 with 12 elements, I got 23,608. Is that right?
Could you write down how you got that.
Case 1 or 12:      2 x N_11(4) = 2 x 3676             = 7352
Case 2 or 11:      2 x N_10(4) = 2 x 1648            = 3296
Case 3 or 10:      2 x N_9(4) x 2 = 2 x 844 x 2      = 3376
Case 4 or 9:      2 x N_8(4) x 5 = 2 x 376 x 5       = 3760
Case 5 or 8:      2 x N_7(4) x 14 = 2 x 152 x 14 = 4256
Case 6 or 7:      2 x N_6(4) x 42 = 2 x 56 x 42      = 1568

7352 + 3296 + 3376 + 3760 + 4256 + 1568 = 23,608
>>  For depth=5 with 12 elements, I got 23,608. Is that right?
I don't think that is correct, because that number isn't divisible by 32.

I don't see what your Case numbers represent ad I don't see how you are calculating them.

What would your total be for 8 elements depth of 5?
For depth=5 with 12 elements, I get     32 x 3 x 4 x 6 x 7 x 8 x 10  = 1,290,240
@pzozulka ,
Are  your nodes labelled or not?
Yes. 1,2,3,...,11,12.
Right now I'm getting 26,872 as my total.
As for the cases, you start with node 1 (or 12 for symmetry). For this case you have to count the number of possible different looking trees with 11 remaining nodes at height 4 since the root is already 1 and your right subtree drops one level and has 11 remaining nodes. So recursively this problem got a little bit easier. For this case alone, you need to calculate, recursively until you get down to calculating the base case which I assume would be 5 nodes at same height of 4. You can't go lower than 5 nodes as it takes a max of 5 nodes to achieve height of 4.

Then you move on to the next case which is root 2 (or 11 for symmetry). You left subtree is only 1, so doesn't really count. Your right subtree has 10 nodes. So again, calculate what N_10(4) is - how many diff looking trees at height 4 with 10 elements can u have.

You do this recursively for all possible cases. Then add all cases together to get your answer.

This is the method I used.
ASKER CERTIFIED SOLUTION
Avatar of d-glitch
d-glitch
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Here is the Python code:
# Initialize the Table
Tree = [[0 for n in range(16)] for d in range(13)]

# Define the function
def calc( d, n):
#    print( 'Calculate Tree( ', d, n, ') =====================')
    value = 0
    for Ln in range( n-1, d-1, -1):     # Ln elements in the essential subtree
        factor = Tree[d-1][Ln]
#        print ( 'factor', d-1, Ln, factor)
        tot = 0
        for Rd in range(0, d-1):
            tot = tot + 2*Tree[Rd][n-1-Ln]
#            print( '- x2 -', Rd, n-1-Ln, Tree[Rd][n-1-Ln], tot)
        Rd = d-1
        if Ln > n-1-Ln:
            tot = tot + 2*Tree[Rd][n-1-Ln]
#            print( '- x2 -', Rd, n-1-Ln, Tree[Rd][n-1-Ln], tot)
        if Ln == n-1-Ln:
            tot = tot + Tree[Rd][n-1-Ln]
#            print( '- x1 -', Rd, n-1-Ln, Tree[Rd][n-1-Ln], tot)
        value = value + factor*tot
#        print ( factor*tot)
#    print( 'Final ==>  ', value)
    return value       
        
# Seed the Table
Tree[0][0] = 1
Tree[0][1] = 1

# Fill in the Table -- Top to Bottom -- Left to Right
for d in range( 1, 13):
    print ('Row  ', d)
    for n in range(1, 16):
        if n > d:
            if n < 2**(d+1):
                Tree[d][n] = calc( d, n)

# Print the Final Table
print( ' ')
print( ' ')
for d in range( 13):
    print( Tree[d]) 

Open in new window

And here is the output:
 
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 4, 6, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 8, 20, 40, 68, 94, 114, 116, 94, 60, 28, 8, 1]
[0, 0, 0, 0, 0, 16, 56, 152, 376, 844, 1744, 3340, 5976, 10040, 15856, 23460]
[0, 0, 0, 0, 0, 0, 32, 144, 480, 1440, 4056, 10856, 27672, 67616, 159184, 362280]
[0, 0, 0, 0, 0, 0, 0, 64, 352, 1376, 4736, 15248, 47104, 140640, 407360, 1148560]
[0, 0, 0, 0, 0, 0, 0, 0, 128, 832, 3712, 14272, 50784, 172640, 568832, 1828832]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 256, 1920, 9600, 40576, 156864, 575104, 2036416]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 512, 4352, 24064, 110592, 459648, 1797504]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1024, 9728, 58880, 291840, 1294592]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2048, 21504, 141312, 750592]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4096, 47104, 333824]

Open in new window

As a check, I filled out the table to  d=8  and  n=512 and totaled across each row.
This should give you the number of trees as a function of depth.

I got:
d=0   2
d=1   3
d=2   21
d=3   651
d=4   457653
d=5   210065930571
d=6   44127887745696109598901
d=7   1947270476915296449559659317606103024276803403
d=8   3791862310265926082868235028027893277370233150300118107846437701158064808916492244872560821

Open in new window

This is essentially identical to https://oeis.org/A001699

I start out with a 2, 3, instead of 1, 1, 3, because I combined Null tree [d=?, n=0] with the [d=0, n=1] tree.