Given an integer n, return all the structurally unique BST's (binary search trees),…
- User
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.
- Assistant
To solve the problem of generating all structurally unique Binary Search Trees (BSTs) with
nnodes containing unique values from1ton, we can use a recursive approach. The idea is to consider each number in the range as the root of the BST, and then recursively generate all possible left and right subtrees.Here's a step-by-step explanation and a Python implementation of the solution:
Step-by-Step Explanation
-
Understanding BST Properties:
- In a BST, for any given node with value
val, all nodes in the left subtree have values less thanval, and all nodes in the right subtree have values greater thanval.
- In a BST, for any given node with value
-
Recursive Generation:
- Base Case: If
start > end, there's no number to construct the subtree, so we return[None]indicating an empty subtree. - Recursive Case:
- Iterate through each number
ifromstarttoendand consider it as the root. - Recursively generate all possible left subtrees using the numbers less than
i. - Recursively generate all possible right subtrees using the numbers greater than
i. - Combine each left and right subtree with the current root
ito form a new BST.
- Iterate through each number
- Base Case: If
-
Combining Trees:
- For each possible root, combine every left subtree with every right subtree to form all unique BSTs rooted at that number.
-
Final Output:
- The recursion builds up all possible trees, and the final result is a list of all unique BSTs.
Python Implementation
Below is the Python code implementing the above approach. It uses a helper function
generateto recursively build the trees. TheTreeNodeclass represents each node in the BST.from typing import List, Optional from dataclasses import dataclass # Definition for a binary tree node. @dataclass class TreeNode: val: int left: Optional['TreeNode'] = None right: Optional['TreeNode'] = None class Solution: def generateTrees(self, n: int) -> List[Optional[TreeNode]]: if n == 0: return [] def generate(start: int, end: int) -> List[Optional[TreeNode]]: trees = [] if start > end: trees.append(None) return trees # Iterate through all values as the root for root_val in range(start, end + 1): # Generate all possible left subtrees left_trees = generate(start, root_val - 1) # Generate all possible right subtrees right_trees = generate(root_val + 1, end) # Combine left and right subtrees with the current root for left in left_trees: for right in right_trees: root = TreeNode(root_val) root.left = left root.right = right trees.append(root) return trees return generate(1, n) # Example Usage: # To print all unique BSTs for n = 3, you can use the following code: def print_tree(node: Optional[TreeNode], prefix: str = ""): if not node: print(prefix + "None") return print(prefix + f"TreeNode({node.val})") if node.left or node.right: print_tree(node.left, prefix + " L--") print_tree(node.right, prefix + " R--") if __name__ == "__main__": sol = Solution() all_trees = sol.generateTrees(3) for idx, tree in enumerate(all_trees, 1): print(f"Tree {idx}:") print_tree(tree) print("-" * 20)Explanation of the Example Usage
The
print_treefunction is a helper to visualize the BSTs generated forn = 3. When you run the code, it will print all 5 unique BSTs that can be constructed with values from 1 to 3.Complexity Analysis
- Time Complexity: The number of unique BSTs with
nnodes is given by then-th Catalan number, which is approximately (O(4^n / n^{3/2})). Generating all trees involves constructing each unique structure, leading to similar exponential time complexity. - Space Complexity: The space complexity is also proportional to the number of unique BSTs, which is exponential in
n.
Conclusion
This recursive approach efficiently generates all structurally unique BSTs by leveraging the properties of BSTs and systematically combining possible left and right subtrees for each potential root. The provided Python implementation can be used directly or adapted to other programming languages as needed.
-