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?
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?
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
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
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 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.
ASKER
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.
Could you write down how you got that.
ASKER
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
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?
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?
Are your nodes labelled or not?
ASKER
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.
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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])
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]
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:
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.
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
This is essentially identical to https://oeis.org/A001699I 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.
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