Unique Binary Search Trees II
Problem Description
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]]
Constraints:
1 <= n <= 8
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The problem requires generating all unique binary search trees (BSTs) that store values 1 to n. The strategy hinges on picking each number as a root and recursively constructing all possible left and right subtrees.
The problem can be divided as follows:
- Choose each number
ifrom 1 tonto serve as the root. - The left subtree will consist of nodes from 1 to
i-1. - The right subtree will consist of nodes from
i+1ton. - Recursively generate all unique BSTs for these left and right subtrees, and combine them to form the required trees.
Code:
- Time Complexity: O(4^n / sqrt{n}) - There can be an exponential number of trees.
- Space Complexity: O(4^n / sqrt{n}) - For the storage of trees.
2. Dynamic Programming Approach
Intuition:
Instead of recalculating solutions for the same subproblems multiple times, we can use a dynamic programming strategy to store results of previously solved problems in a memoization form. This helps reduce redundant computations but is more complex to set up and typically provides similar time complexity benefits for this specific problem.
Code:
- Time Complexity: O(4^n / sqrt{n}) - Results are stored for repeated subproblems.
- Space Complexity: O(n ^ 2) - Due to the memoization matrix.