THIS MAY HELP!!!
the number of binary search trees with n nodes, C(n), is the nth Catalan number. Here's why:
Consider the integers 1, 2, ..., n. The number of trees with root k is C(k-1)C(n-k), because there are k-1 integers below k and n-k above k. Then the total is found by adding these up for k from 1 to n:
C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0)
with the trivial cases given by C(0)=1 and C(1)=1.
the number of binary search trees with n nodes, C(n), is the nth Catalan number. Here's why:
Consider the integers 1, 2, ..., n. The number of trees with root k is C(k-1)C(n-k), because there are k-1 integers below k and n-k above k. Then the total is found by adding these up for k from 1 to n:
C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0)
with the trivial cases given by C(0)=1 and C(1)=1.
No comments:
Post a Comment