All possible full binary trees

Dynamic Programming Tree Recursion Memoization Binary Tree

82.8% acceptance

Feb 27, 2026

5237

368

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0. Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order. A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

/*
 * Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.
 * Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.
 * A full binary tree is a binary tree where each node has exactly 0 or 2 children.
 * Example 1:
 * Input: n = 7
 * Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
 * Example 2:
 * Input: n = 3
 * Output: [[0,0,0]]
 * Constraints:
 * 1 <= n <= 20
 */

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn all_possible_fbt(n: i32) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    if n % 2 == 0 { return vec![]; }
    if n == 1 { return vec![Some(Rc::new(RefCell::new(TreeNode::new(0))))]; }
    let mut res = vec![];
    let mut k = 1i32;
    while k < n - 1 {
      let lefts = Self::all_possible_fbt(k);
      let rights = Self::all_possible_fbt(n - 1 - k);
      for l in &lefts {
        for r in &rights {
          let mut root = TreeNode::new(0);
          root.left = l.clone();
          root.right = r.clone();
          res.push(Some(Rc::new(RefCell::new(root))));
        }
      }
      k += 2;
    }
    res
  }
}