Unique binary search trees ii

Dynamic Programming Backtracking Tree Binary Search Tree Binary Tree

62.0% acceptance

Feb 27, 2026

7936

583

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
  pub fn generate_trees(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    if n == 0 {
      return vec![];
    }
    Self::generate(1, n)
  }
  
  fn generate(start: i32, end: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    let mut result = Vec::new();
    
    if start > end {
      result.push(None);
      return result;
    }
    
    for i in start..=end {
      let left_trees = Self::generate(start, i - 1);
      let right_trees = Self::generate(i + 1, end);
      
      for left in &left_trees {
        for right in &right_trees {
          let mut root = TreeNode::new(i);
          root.left = left.clone();
          root.right = right.clone();
          result.push(Some(Rc::new(RefCell::new(root))));
        }
      }
    }
    
    result
  }
}