Unique binary search trees

Math Dynamic Programming Tree Binary Search Tree Binary Tree

63.3% acceptance

Jan 12, 2026

10971

446

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_trees(n: i32) -> i32 {
    let n = n as usize;
    let mut dp = vec![0; n + 1];
    dp[0] = 1;
    dp[1] = 1;
    
    for i in 2..=n {
      for j in 1..=i {
        dp[i] += dp[j-1] * dp[i-j];
      }
    }
    
    dp[n]
  }
}