Leetcode Problem 96. Unique Binary Search Trees

96. Unique Binary Search Trees

Leetcode Solutions

Dynamic Programming Approach to Count Unique BSTs

  1. Initialize an array G with n+1 elements, all set to 0.
  2. Set G[0] and G[1] to 1, as the base cases.
  3. For each number j from 2 to n (inclusive), compute G[j] as follows: a. Initialize G[j] to 0. b. For each i from 1 to j (as the root), increment G[j] by G[i-1] * G[j-i].
  4. Return G[n] as the result, which is the number of unique BSTs that can be formed with n distinct nodes.
UML Thumbnail

Mathematical Deduction Approach to Count Unique BSTs

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...