BST Practice Question
Duration: 2 min
This video lesson is available to enrolled students.
AI Summary
An AI-generated summary of this video lecture.
The video features an educational lecture on data structures, specifically focusing on counting distinct binary search trees. The instructor, Sanchit Jain, solves a multiple-choice question asking for the number of distinct BSTs that can be formed with 4 distinct keys. He utilizes the Catalan number formula to derive the solution step-by-step on a whiteboard.
Chapters
0:00 – 1:37 00:00-01:37
The video begins with a slide displaying the 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, Sanchit Jain, appears in the bottom right corner and writes the Catalan number formula $ rac{2n C_n}{n+1}$ on the board. He substitutes $n=4$ to get $ rac{8 C_4}{5}$. He expands this into factorials: $ rac{8!}{4!4!5}$. He then expands the numerator to $8 imes 7 imes 6 imes 5 imes 4!$ and cancels terms with the denominator. The simplified expression becomes $ rac{8 imes 7 imes 6}{4 imes 3 imes 2 imes 1}$. After calculating the values, he arrives at the result 14. He marks option (B) as the correct answer. The Knowledge Gate logo is visible throughout the background.
The lecture demonstrates a standard combinatorial approach to solving binary tree counting problems. By applying the Catalan number formula, the instructor efficiently calculates the number of structurally unique trees without needing to draw them all. The step-by-step factorial expansion and cancellation serve as a clear method for students to follow for similar problems involving $n$ nodes.