0096.Unique Binary Search Trees

Link: 96. Unique Binary Search Trees - Medium
Track: Amazon Tag

Question

• Given integer n
• From 1 to n, build binary search tree
• Return all possible number of BST

Edge Case

• n = 0, return 1
• n = 1, return 1

---

Method 1 - DP
Method 2

Method

• Key insight:
  • dp[i] = number of unique BSTs that can be built usign i nodes

Approach

• One node as root

• So, n - 1 separate to left and right tree

• For i nodes, choose a root. Then split n-1 nodes:

  • iterate possible number of left
    • right size = i - 1 - left

Complexity

• Time Complexity: O($n^2$)
• Space Complexity: O(n)

Code

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1) # [0, n]
 
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            total = 0
            for left in range(i):
                right = i - left - 1
                total += dp[right] * dp[left]
            
            dp[i] = total
 
        return dp[n]

---

History

• Feb-16-2026 Peeked
  • No idea