fork download
copy 
  1. # Q: How many total number of binary search trees are possible
  2. # with 6 vertices?
  3. # A: 132.
  4.  
  5. # Recurrence formula:
  6. # b(0) = 1,
  7. # b(n) = b(0)b(n-1) + b(1)b(n-2) + ... + b(n-1)b(0), n > 0.
  8.  
  9. # Generally speaking,
  10. # b(n) = (2n)! / ((n+1)!n!), where n is nonnegative.
  11.  
  12. b = []
  13. b.append(1)
  14. n = 10
  15.  
  16. for k in range(1, n+1):
  17. 	s = 0
  18. 	for j in range(k):
  19. 		s = s + b[j] * b[k-j-1]
  20. 	b.append(s)
  21.  
  22. print(b)
Success #stdin #stdout 0.09s 14156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
https://ideone.com/fxLFRU
Compute the total number of binary search trees
language:
Python 3 (python  3.12)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!