!!!!!!!NOTE: IT WLL BE A LFESAVER!!!!!!! Problem Definition We count the number
ID: 3631341 • Letter: #
Question
!!!!!!!NOTE: IT WLL BE A LFESAVER!!!!!!!
Problem Definition
We count the number of binary trees with N nodes, denoted by T(N).
The key observation is that the given the root node, the left and right subtrees are (possibly
empty) binary trees. So for a tree with N +1 nodes, we need to choose a left subtree of k nodes and
a right subtree of N k nodes. So the number of trees satisfies the recursion
T(0) = 1
This type of recursion is called a convolution. One can solve this for T(N) using the method of
generating functions (known also as the z transform) but this is not our topic here.
We verify this recursion
T(0) = 1
T(1) = T(0)T(0) = 1
T(2) = T(0)T(1) + T(1)T(0) = 1 + 1 = 2
T(3) = T(0)T(2) + T(1)T(1) + T(2)T(0) = 2 + 1 + 2 = 5
T(4) = T(0)T(3) + T(1)T(2) + T(2)T(1) + T(3)T(0) = 5 + 2 + 2 + 5 = 14
And we program this recursion to get
0 1
1 1
2 2
3 5
....
....
19 1767263190
20 6564120420
...
99 227508830794229349661819540395688853956041682601541047340
An 32 bit integer can not store the number of trees when N > 19, so we need a large integer
class.
Assignment
• Write an ANSI C++ program that calculates the number of binary trees up to 200 nodes.
Important Points
• Within your code, implement a LargeInteger class that can do addition and multiplication with
large integers.
• You are expected to use C++ with as many related features as possible. This can (but does
not have to) include operator overloading, classes, dynamic memory management, templates.
• Make sure that your output format is exactly as above example, that is each line i for i 2 [0, 200]
should have i T(i), and only that. This is important for the automated testing of correctness
of your program.
Bonuses and Beyond
• Bonus: Write a program to draw all 429 binary trees with N = 7 nodes. (Deliver the drawings
as one separate postscript file.)
– How to draw trees in C++ using postscript? This will be covered in the problem session
and we will provide more information next week on the course web page.
• Bonus: Derive an explicit formula for T(N) (Hard). (Deliver your derivation as a separate pdf
file (scanned or latex))
• For the Connoisseur: Show or disprove that T(N) that is odd if and only if N = 2k -1for
positive integer k.
Explanation / Answer
int row = board[column]; while(lineNotFound && rowRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.