Sponsored
Sponsored
This approach involves dividing the set of integers from 1 to n into left and right subtrees recursively for each possible root value. For each possible root node, the values less than the root form the left subtree and the values greater than the root form the right subtree. We repeat this process recursively to construct all unique BSTs by selecting each number in the range as the root.
Time Complexity: O(4^n / √n) where n is the number of nodes because it involves generating all unique trees which is a Catalan number problem.
Space Complexity: O(4^n / √n) for storing the results.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var generateTrees = function(n) {
7 if (n == 0) return [];
8 return generateTreesRange(1, n);
9};
10
11function generateTreesRange(start, end) {
12 let allTrees = [];
13 if (start > end) {
14 allTrees.push(null);
15 return allTrees;
16 }
17
18 for (let i = start; i <= end; i++) {
19 let leftTrees = generateTreesRange(start, i - 1);
20 let rightTrees = generateTreesRange(i + 1, end);
21
22 for (const left of leftTrees) {
23 for (const right of rightTrees) {
24 const currentTree = new TreeNode(i);
25 currentTree.left = left;
26 currentTree.right = right;
27 allTrees.push(currentTree);
28 }
29 }
30 }
31 return allTrees;
32}
33This JavaScript code utilizes a recursive mechanism to generate all unique BSTs. The 'generateTreesRange' function recursively creates trees by making selections for the root node, identifying left and right subtrees.
This approach involves leveraging dynamic programming to store results of previously evaluated subproblems to optimize the recursive solution. We maintain a memoization table to store precalculated trees for specific ranges, aiding efficient calculation by reducing the re-computation of the same subproblems.
Time Complexity: O(4^n / √n) due to solving subproblems exactly once.
Space Complexity: O(4^n / √n) for storing the memoized results.
1import java.util.*;
This Java code implements memoization using a HashMap to cache results of recursive subproblem solutions, optimizing performance by reducing redundant evaluations.