Thumbnail
Access Restriction
Subscribed

Author Rolfe, Timothy
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Binary search tree ♦ Catalan number ♦ Optimization
Abstract This article examines the recurrence obtained for Catalan numbers based on their description of the number of unique binary search tree structures possible with n distinct keys. The straightforward recurrence obtained, when transformed into a recursive method, obtains the solution in $3^{n}$ method invocations. With a small change based on symmetry, this can be changed to obtain the solution in $2^{n}$ method invocations. Of course, one can obtain the solution in massively fewer operations $(O(n^{2}))$ in a dynamic programming/memoized solution.
Description Affiliation: Eastern Washington University, Washington (Rolfe, Timothy)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2013-12-01
Publisher Place New York
Journal Inroads
Volume Number 2
Issue Number 4
Page Count 5
Starting Page 33
Ending Page 37


Open content in new tab

   Open content in new tab
Source: ACM Digital Library