Last updated on January 29th, 2025 at 02:19 am
Here, we see a Unique Binary Search Trees II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, Tree
Level of Question
Medium

Unique Binary Search Trees II LeetCode Solution
Table of Contents
1. Problem Statement
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.
Example 1:
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1
Output: [[1]]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Tree Depth First Search”. This is because the problem involves recursively constructing all possible binary search trees (BSTs) for a given range of numbers. The recursion explores all possible left and right subtrees for each root value, which is characteristic of a depth-first traversal.
3. Code Implementation in Different Languages
3.1 Unique Binary Search Trees II C++
class Solution { public: vector<TreeNode*> generateTrees(int n) { if(n == 0) return vector<TreeNode *>(1, NULL); vector<vector<vector<TreeNode*>>> subtree(n+2, vector<vector<TreeNode*>>(n+2, vector<TreeNode*>())); for(int i=1; i<=n+1; ++i){ subtree[i][i].push_back(new TreeNode(i)); subtree[i][i-1].push_back(NULL); } for(int l=2; l<=n; ++l){ for(int i=1; i<=n-l+1; ++i){ for(int j=i; j<=i+l-1; ++j){ for(int k=0; k<subtree[j+1][i+l-1].size(); ++k){ for(int m=0; m<subtree[i][j-1].size(); ++m){ TreeNode *T = new TreeNode(j); T->left = subtree[i][j-1][m]; T->right = subtree[j+1][i+l-1][k]; subtree[i][i+l-1].push_back(T); } } } } } return subtree[1][n]; } };
3.2 Unique Binary Search Trees II Java
class Solution { public List<TreeNode> generateTrees(int n) { return generateTrees(1,n); } public List<TreeNode> generateTrees(int start,int end){ List<TreeNode> trees = new ArrayList<TreeNode>(); if(start>end){ trees.add(null); return trees;} for(int rootValue=start;rootValue<=end;rootValue++){ List<TreeNode> leftSubTrees=generateTrees(start,rootValue-1); List<TreeNode> rightSubTrees=generateTrees(rootValue+1,end); for(TreeNode leftSubTree:leftSubTrees){ for(TreeNode rightSubTree:rightSubTrees){ TreeNode root=new TreeNode(rootValue); root.left=leftSubTree; root.right=rightSubTree; trees.add(root); } } } return trees; } }
3.3 Unique Binary Search Trees II JavaScript
var generateTrees = function(n) { const constructArray = (start, end) => { const result = []; if(start > end){ return [null]; } if(start===end){ return [new TreeNode(start)]; } if(end-start===1){ const first = new TreeNode(start, null, new TreeNode(end)); const second = new TreeNode(end, new TreeNode(start), null); return [first, second]; } for(let i=start; i<=end; i++){ const leftSide = constructArray(start, i-1); const rightSide = constructArray(i+1, end); leftSide.forEach(ls => { rightSide.forEach(rs => { const tree = new TreeNode(i, ls, rs); result.push(tree); }) }) } return result; } return constructArray(1,n); };
3.4 Unique Binary Search Trees II Python
class Solution(object): def generateTrees(self, n): def node(val, left, right): node = TreeNode(val) node.left = left node.right = right return node def trees(first, last): return [node(root, left, right) for root in range(first, last+1) for left in trees(first, root-1) for right in trees(root+1, last)] or [None] return trees(1, n)
4. Time and Space Complexity
Space Complexity | |
C++ | O(n2) + O(n) |
Java | O(n) |
JavaScript | O(n) |
Python | O(n) |