ข้อนี้สามารถมองเป็นคำถามว่ามี Binary Search Tree ที่มีตัวเลข $1$ ถึง $N$ กี่แบบ (จากเงื่อนไขที่ 2 และ 3)

Binary Search Tree คือ Binary Tree ที่ตัวทุกตัวที่อยู่ใน Subtree ของปมลูกซ้ายของแต่ละปมมีค่าน้อยกว่า และที่อยู่ฝั่งขวามีค่ามากกว่า

เคส $N \leq 10$

กำหนดให้ $F(N)$ เป็นคำตอบว่ามี Binary Search Tree ขนาด $N$ กี่แบบเป็น

สำหรับ $N=1$ จะได้ $F(1)=1$ เพราะมีปมเดียว

สังเกตว่าในต้น Binary Search Tree ขนาด $N$ จะเลือกรากได้ $N$ ตัว คือเลือกตัวที่ $1,2,\dots, N$ มาเป็นราก

เมื่อเลือกรากเป็นตัวเลข $i$ แล้วจะสามารถสร้าง Subtree ในปมลูกซ้ายได้ $F(i-1)$ (เพราะตัวเลข $1,2, \dots, i$ จะต้องอยู่ในฝั่งซ้ายตามเงื่อนไข 3) และในฝั่งขวาจะสร้างได้ $F(N-i)$ วิธี

ดังนั้นจะได้ว่า $F(N) = \Sigma_{i=1}^N F(i-1)F(N-i)$

หากเราคำนวณ $F(N)$ ด้วยวิธี Recursion แบบธรรมดาจะได้ว่าต้องใช้เวลาไม่เกิน $\mathcal{O}(2^N)$ ซึ่งเร็วเพียงพอสำหรับ $N \leq 10$ แต่ช้าไปสำหรับเคสต่อๆ มา

(ในการคำนวณ $F(N)$ ต้องคำนวณ $F(1), F(2), \dots,F(N-1)$ ดังนั้นจะได้ว่าใช้เวลา $T(N)= \Sigma_{i=1}^N T(i) + \mathcal{O}(N)$ ซึ่งพิสูจน์ด้วย Induction ได้ว่าเป็น $\mathcal{O}(2^N)$)

เคส $N \leq 10000$

สำหรับเคสต่อมาสามารถใช้ Dynamic Programming บันทึกค่า $F(i)$ ที่ถูกคำนวณไว้แล้ว จะทำให้ไม่ต้องคำนวณค่า $F(i)$ ใหม่ทุกครั้งที่ต้องเรียกใช้

ในการคำนวณ $F(i)$ หาก $F(1),F(2),\dots, F(i-1)$ ถูกคำนวณไว้แล้วจะสามารถใช้สูตร $F(N) = \Sigma_{i=1}^N F(i-1)F(N-i)$ เพื่อคำนวณ $F(i)$ ในเวลา $\mathcal{O}(i)$

ดังนั้นหากจะคำนวณ $F(N)$ จะสามารถคำนวณ $F(1), F(2), \dots, F(N)$ ตามลำดับซึ่งจะใช้เวลา $\Sigma_{i=1}^N \mathcal{O}(i) = \mathcal{O}(N^2)$ ซึ่งเพียงพอสำหรับข้อนี้

เพิ่มเติม

จำนวน Binary Search Tree $F(N)$ คือ Catalan Number ตัวที่ $N$ ซึ่งมีสูตรคือ $C_N = \frac{1}{N+1} {2N \choose N}$