BST Practice Question

AI Summary

An AI-generated summary of this video lecture.

This lecture solves a binary search tree (BST) counting problem by introducing Catalan numbers. It begins with the example of 3 distinct keys, showing that there are 5 possible BST structures. The main question asks how many distinct BSTs can be created from 4 distinct keys, with options (A) 4, (B) 14, (C) 24, and (D) 42. The instructor introduces the Catalan number formula in both recursive form, C_n = sum_{i=0}^{n-1} C_i * C_{n-i-1}, and closed form, (2n choose n)/(n+1) or (2n)!/((n+1)! * n!). A table is built for f(N) where N represents the number of keys: f(0)=1, f(1)=1, f(2)=2, and f(3)=5. For N=4, the instructor considers each key (1, 2, 3, or 4) as the root and multiplies the number of left-subtree combinations by right-subtree combinations: C_0*C_3 + C_1*C_2 + C_2*C_1 + C_3*C_0 = 5 + 2 + 2 + 5 = 14. Option (B) 14 is circled as the correct answer.

Chapters

1. 0:00 – 2:00 00:00-02:00

   The video opens with a practice question asking how many distinct BSTs can be constructed with 3 distinct keys, displaying the 5 possible tree structures for N=3. It then transitions to the main question: 'How many distinct binary search trees can be created out of 4 distinct keys?' with options (A) 4, (B) 14, (C) 24, and (D) 42. The instructor writes 'Formula of catalan number' in red, showing the recurrence c_n = sum_{i=0}^{n-1} c_i * c_{n-i-1} and the closed form (2n choose n)/(n+1). A two-column table headed 'N' and 'f(n)' is drawn, with the row N=0 entered as f(0)=1.

2. 2:00 – 5:00 02:00-05:00

   The instructor builds the table step by step, writing N=1 with f(1)=1=C_1 and continuing to calculate values for increasing N. The closed-form formula C_n = (2n)!/((n+1)! * n!) is displayed on the right side of the screen. For N=3, the instructor draws explicit BST structures using keys 1, 2, and 3 to visualize why f(3)=5. The recursive formula C_n = sum_{i=0}^{n-1} C_i * C_{n-i-1} is written alongside the table, connecting the manual enumeration to the general Catalan number recurrence.

3. 5:00 – 10:00 05:00-10:00

   The instructor calculates f(2)=2 and confirms f(3)=5 by summing products of left and right subtree combinations. For N=4, the instructor lists all possible roots (1, 2, 3, and 4) and draws tree diagrams for each root choice. The breakdown shows that choosing key 1 as root gives C_0*C_3 combinations, key 2 gives C_1*C_2, key 3 gives C_2*C_1, and key 4 gives C_3*C_0. The table now shows f(0)=1, f(1)=1, f(2)=2, and f(3)=5, with the Catalan recurrence C_n = sum C_i * C_{n-1-i} displayed on the right.

4. 10:00 – 12:58 10:00-12:58

   The final calculation sums the products for N=4: C_0*C_3 + C_1*C_2 + C_2*C_1 + C_3*C_0 = 5 + 2 + 2 + 5 = 14. The instructor writes f(4)=14 in the table and circles option (B) 14 as the correct answer. The completed whiteboard shows the full table from N=0 to N=4, four BST structures drawn at the bottom corresponding to roots 1 through 4, and the Catalan number formula C_n = sum_{i=0}^{n-1} C_i * C_{n-i-1} on the right side, verifying that the recursive counting matches the closed-form Catalan number.

The central concept is that the number of distinct BSTs with n keys equals the nth Catalan number. The teaching flow moves from a concrete example (N=3, five trees) to the general formula. The recursive method works by choosing each key as root: if key i is root, the left subtree has (i-1) keys and the right subtree has (n-i) keys, contributing C_{i-1} * C_{n-i} combinations. Summing over all roots gives the recurrence. The closed form (2n)!/((n+1)! * n!) provides a direct calculation. For N=4, the answer 14 is verified both by the recurrence and by explicit enumeration of root cases. Key exam takeaway: recognize BST counting problems as Catalan number applications, and be able to compute small values (1, 1, 2, 5, 14) from the recurrence.