95. Unique Binary Search Trees II

MediumTreeBinary Search TreeDynamic ProgrammingBacktrackingBinary Tree

Problem Description

The problem asks us to generate all structurally unique binary search trees (BSTs) that can be constructed with n uniquely valued nodes, where each node's value is a unique integer from 1 to n. Structurally unique means that the trees' shape or structure must be different; simply rearranging nodes without changing the parents and children does not count as unique. The goal is not only to count these trees but to actually construct each distinct tree and return a collection of them.

Flowchart Walkthrough

To determine the suitable algorithm pattern for solving Leetcode problem 95, "Unique Binary Search Trees II," let's consult the provided algorithm flowchart. Here’s the step-by-step analysis:

Is it a graph?

Yes: Though not a traditional graph problem, binary search trees inherently involve structured node and edge relationships like graphs.

Need to solve for kth smallest/largest?

No: The goal is not to find a specific smallest or largest element.

Involves Linked Lists?

No: The problem is about binary search trees, not linked lists.

Does the problem have small constraints?

Yes: The problem generally implies generating all unique BSTs for a given small number of nodes (n is typically manageable, suggesting we can handle comprehensively constructing these trees).

Brute force / Backtracking?

Yes: This problem inherently requires generating multiple tree structures conditioned on each node choice, which fits well within the brute force or backtracking paradigms.

Conclusion: Based on the identification of the problem structure via the flowchart, backtracking is the appropriate strategy for this problem. The task requires constructing all unique binary search trees from a sequential set of numbers, making it necessary to explore multiple branching decisions (like placing each number as the root and recursively constructing left and right subtrees), aligning well with the backtracking method.

Intuition

The intuition behind the solution for generating all structurally unique BSTs for n unique values involves understanding the properties of BSTs and using recursion to build all possible trees. The main property of a BST is that the left subtree of a node contains only nodes with keys less than the node's key, and the right subtree only contains nodes with keys greater than the node's key.

Here's how we can arrive at the solution approach:

We know that the root can be any node with a value from 1 to n.
Once we select a value i for the root, all values from 1 to i-1 must be in the left subtree, and all values from i+1 to n must be in the right subtree, due to the properties of BSTs.
To generate all unique left and right subtrees, we can use recursion on the respective ranges. The recursive call will generate all possible left subtrees for the values smaller than i and all possible right subtrees for the values larger than i.
We combine each left subtree with each right subtree to form a unique BST with i as the root.

This approach utilizes the power of recursion to break down the problem into smaller subproblems, namely constructing all possible subtrees for a given range and then combining them to form larger and complete BSTs.

By defining a recursive function gen(left, right), which takes a range of values and returns all possible BSTs within that range, we can use this function to explore all possible combinations that satisfy BST properties. This recursion forms the backbone of our solution. It starts by generating all trees for 1-n, and for each of those, it recursively generates left and right subtrees for the remaining ranges until the ranges are empty, at which point it will use None to represent the absence of a node, indicating that the recursion has bottomed out.

This careful assembly of left and right subtrees around each possible root, following BST conditions, will yield all structurally unique BSTs containing n nodes.

Learn more about Tree, Binary Search Tree, Dynamic Programming, Backtracking and Binary Tree patterns.

Solution Approach

The solution uses a recursive helper function gen(left, right) which is designed to generate all possible unique BSTs composed of node values ranging from left to right, inclusive. Here's the step-by-step explanation of the gen function and the overall solution approach:

Base Case: If the left limit is greater than the right limit, it means there are no values to create a node, so we append None to the list of answers. This corresponds to the base case of the recursion which effectively handles the creation of empty trees (required at the leaf nodes of the final BSTs).
Recursive Case: The recursive case is when left <= right, meaning we have at least one value to create a node with.
Generating Roots: A loop runs from left to right including both ends. Each iteration of the loop represents choosing a different value as the root of the BST from the given range.
Divide and Conquer: For each potential root value i, we recursively call gen to create all possible left subtrees with values from left to i-1 and right subtrees with values from i+1 to right. This is where the divide-and-conquer algorithm comes into play, breaking the original problem into smaller subproblems, each capable of being solved independently.
Constructing Trees: After the recursive calls, we iterate over all combinations of left and right subtrees. For each combination, a new tree node is created with the value i (which we selected as a root earlier) and the left and right pointers set to the current left and right subtree from the combinations. These new trees are then added to the ans list.
List of Tree Nodes: The helper function gen eventually returns a list of TreeNode objects. Each TreeNode is the root of a structurally unique BST.
Final Result: The generateTrees function starts the recursive process by calling gen(1, n) and returns the list it receives from this call. The final return value is a list of all unique BSTs with node values from 1 to n.

The algorithm makes use of the fundamental properties of BSTs for the divide-and-conquer strategy and employs recursion efficiently to construct all possible outcomes. The data structure used is the TreeNode class, which represents the nodes in a BST.

In summary, the solution leverages recursion to explore every single potential node value as a root and attaches to it every combination of left and right subtrees that the sub-ranges can produce, ensuring that all unique BST structures are explored.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through a small example to illustrate the solution approach using n = 3. This means we want to generate all structurally unique BSTs using node values {1, 2, 3}.

Step 1: Call the Main Function

We start by calling gen(1, 3) because our range of values is from 1 to 3.

Step 2: Loop Through Each Value as Root

We then establish a loop for selecting the root value from the candidates 1 to 3.

When i = 1, 1 is the root, we have no left subtree (gen(1, 0) returns None) and we need to generate the right subtree with values {2, 3}. The function gen(2, 3) is called for the right subtree.

When i = 2, 2 is the root, we generate the left subtree with value {1} only (gen(1, 1)) and the right subtree with value {3} only (gen(3, 3)).

When i = 3, 3 is the root, we generate the left subtree with values {1, 2} (gen(1, 2)) and there is no right subtree (gen(4, 3) returns None).

Step 3: Recursively Generate Subtrees

For each of these scenarios, we recursively generate the possible left and right subtrees:

For i = 1, gen(2, 3) needs to consider 2 and 3 as potential roots for the right subtree.
For i = 2, since we are considering single elements (1 for left and 3 for right), gen(1, 1) and gen(3, 3) directly return the TreeNode with the corresponding value. These are leaf nodes.
For i = 3, gen(1, 2) considers both 1 and 2 as roots. If 1 is the root, 2 would be its right child (gen(2, 2) returns TreeNode with value 2). If 2 is the root, 1 would be its left child (gen(1, 1) returns TreeNode with value 1).

Step 4: Construct Trees and Combine Subtrees

Now we construct the trees by combining the returned TreeNode(s) for the left and right subtrees with the root. For instance:

With i = 1 as root, combine None as left subtree (since there are no values less than 1) and each TreeNode returned from gen(2, 3) as right subtrees individually.
With i = 2 as root, set the left child to TreeNode with value 1 and right child to TreeNode with value 3.
With i = 3 as root, set the left child to each TreeNode returned from gen(1, 2) and the right child to None.

Step 5: Collect and Return the Results

Each complete tree represents one of the possible structurally unique BSTs that the function is designed to generate. Once all trees have been constructed for all i, the gen function will return the list of root nodes, which forms the output of the generateTrees function.

In summary, for n = 3, we will end up with 5 unique BSTs, which are constructed by the function through recursion and combination of all possible left and right subtrees for each candidate root from values 1 to 3.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def generateTrees(self, n: int) -> List[TreeNode]:
10        # Recursive function to generate all unique BSTs in the range [start, end]
11        def generate(start, end):
12            trees = []  # List to store the trees
13            # Base case: if start is greater than end, there is no tree to add
14            if start > end:
15                trees.append(None)
16            else:
17                # Iterate through each number in the current range as the root
18                for root_value in range(start, end + 1):
19                    # Recursively generate all possible left subtrees with values less than the root
20                    left_trees = generate(start, root_value - 1)
21                    # Recursively generate all possible right subtrees with values greater than the root
22                    right_trees = generate(root_value + 1, end)
23                  
24                    # Nested loops to combine each left and right subtree with the current root node
25                    for left_subtree in left_trees:
26                        for right_subtree in right_trees:
27                            # Create a new tree with the current number as the root
28                            root = TreeNode(root_value, left_subtree, right_subtree)
29                            trees.append(root)
30            return trees
31
32        # Return all possible unique BSTs generated from values 1 to n
33        return generate(1, n)
34

1import java.util.ArrayList;
2import java.util.List;
3
4// Definition for a binary tree node.
5class TreeNode {
6    int val;
7    TreeNode left;
8    TreeNode right;
9  
10    // Constructor to create a node without any children.
11    TreeNode() {}
12  
13    // Constructor to create a node with a specific value.
14    TreeNode(int val) { this.val = val; }
15  
16    // Constructor to create a node with a specific value and given left and right children.
17    TreeNode(int val, TreeNode left, TreeNode right) {
18        this.val = val;
19        this.left = left;
20        this.right = right;
21    }
22}
23
24class Solution {
25    // Generates all structurally unique BSTs (binary search trees) that store values 1...n.
26    public List<TreeNode> generateTrees(int n) {
27        return generateTreesInRange(1, n);
28    }
29
30    // Helper function that generates all structurally unique BSTs for values in the range [start, end].
31    private List<TreeNode> generateTreesInRange(int start, int end) {
32        List<TreeNode> trees = new ArrayList<>();
33        // If start is greater than end, there is no tree to add (empty tree).
34        if (start > end) {
35            trees.add(null);
36        } else {
37            // Try each number as root, and recursively generate left and right subtrees.
38            for (int rootValue = start; rootValue <= end; ++rootValue) {
39                // Generate all left subtrees by considering numbers before the root value.
40                List<TreeNode> leftSubtrees = generateTreesInRange(start, rootValue - 1);
41                // Generate all right subtrees by considering numbers after the root value.
42                List<TreeNode> rightSubtrees = generateTreesInRange(rootValue + 1, end);
43                // Combine left and right subtrees with the current rootValue to form unique BSTs.
44                for (TreeNode leftSubtree : leftSubtrees) {
45                    for (TreeNode rightSubtree : rightSubtrees) {
46                        // Create a new tree node as the root with leftSubtree and rightSubtree as children.
47                        TreeNode root = new TreeNode(rootValue, leftSubtree, rightSubtree);
48                        // Add the newly formed tree to the list of trees.
49                        trees.add(root);
50                    }
51                }
52            }
53        }
54        // Return all possible BSTs formed from values in the range [start, end].
55        return trees;
56    }
57}
58

1#include <vector>
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8
9    // Constructor to initialize a tree node with default values
10    TreeNode() : val(0), left(nullptr), right(nullptr) {}
11
12    // Constructor to initialize a tree node with a specific value
13    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14
15    // Constructor to initialize a tree node with a value and left and right children
16    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
17};
18
19class Solution {
20public:
21    // Main function to generate all structurally unique BSTs (binary search trees) that store values 1 to n
22    std::vector<TreeNode*> generateTrees(int n) {
23        return generateTreesInRange(1, n);
24    }
25
26private:
27    // Helper function that generates all unique BSTs within a specific value range (left to right inclusive)
28    std::vector<TreeNode*> generateTreesInRange(int left, int right) {
29        std::vector<TreeNode*> trees; // Stores the list of unique BSTs for the current range
30        // Base case: if there are no numbers to construct the tree with, add a nullptr to represent empty
31        if (left > right) {
32            trees.push_back(nullptr);
33        } else {
34            // Loop through each number within the range to make it the root of BSTs
35            for (int rootValue = left; rootValue <= right; ++rootValue) {
36                // Recursively generate all possible left subtrees 
37                std::vector<TreeNode*> leftSubtrees = generateTreesInRange(left, rootValue - 1);
38                // Recursively generate all possible right subtrees
39                std::vector<TreeNode*> rightSubtrees = generateTreesInRange(rootValue + 1, right);
40                // Combine the left and right subtrees with the current root node to form unique BSTs
41                for (TreeNode* leftSubtree : leftSubtrees) {
42                    for (TreeNode* rightSubtree : rightSubtrees) {
43                        TreeNode* rootNode = new TreeNode(rootValue, leftSubtree, rightSubtree);
44                        // Add the newly formed BST to the list of BSTs for this range
45                        trees.push_back(rootNode);
46                    }
47                }
48            }
49        }
50        return trees; // Return the list of BSTs generated for this range
51    }
52};
53

1// TreeNode definition representing a node in the binary tree.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8// Generates all structurally unique BSTs (binary search trees) that store values 1 to n.
9function generateTrees(n: number): Array<TreeNode | null> {
10    if (n == 0) return [];
11    // Call the recursive helper to construct the trees.
12    return constructTrees(1, n);
13}
14
15// Helper function that returns an array of all possible BSTs within a range of values.
16function constructTrees(start: number, end: number): Array<TreeNode | null> {
17    let trees: Array<TreeNode | null> = [];
18    if (start > end) {
19        trees.push(null); // Base case: if there are no numbers to add, add null for the tree node.
20        return trees;
21    }
22  
23    // Iterate all numbers from start to end, considering each number as the root.
24    for (let i: number = start; i <= end; i++) {
25        // Recursively construct all possible left and right subtrees.
26        let leftSubtrees: Array<TreeNode | null> = constructTrees(start, i - 1);
27        let rightSubtrees: Array<TreeNode | null> = constructTrees(i + 1, end);
28      
29        // Combine each left and right subtree with the root node 'i'.
30        for (let left of leftSubtrees) {
31            for (let right of rightSubtrees) {
32                // Create the root node with the current value 'i'.
33                let rootNode: TreeNode = { val: i, left: left, right: right };
34                trees.push(rootNode); // Add the formed tree to the list.
35            }
36        }
37    }
38    return trees; // Return all possible trees.
39}
40
41// Here, the TreeNode definition should be present in the global scope to match the existing functions.
42// The TreeNode constructor/class definition is omitted since it is not to be defined outside of a class as per the instructions.
43

Time and Space Complexity

Time Complexity

The time complexity of the given code can be tricky to analyze due to its recursive nature and because it generates all unique binary search trees (BSTs) with n distinct nodes. The number of such trees is given by the nth Catalan number, which is C_n = (2n)! / ((n+1)!n!).

In the worst case, the recursion tree would have a branching factor equal to the maximum number of nodes n, at each node there is a loop that runs from left to right. As we recurse down the tree and back, we create new trees for each possible root node.

For each value of i (from left to right inclusive), we generate all possible left subtrees with gen(left, i - 1) and all possible right subtrees with gen(i + 1, right). Then, for each combination of left and right subtrees, we connect them to a root node with value i. Since the number of combinations for the left and right subtrees is the product of the count of left subtrees and the count of right subtrees, we have a multiplication of possibilities each time we perform this operation.

Considering the above factors, the time complexity is O(n * C_n), where C_n is the nth Catalan number, since we have n possibilities at each level of the recursive stack.

The time taken for all recursive calls can thus be approximated as proportional to the number of unique BSTs generated, which is the Catalan number, times n, giving us a time complexity of O(n * C_n).

Space Complexity

The space complexity consists of the space needed for the output, which stores all unique BSTs, and the space needed for the execution stack during recursion.

The output itself will hold C_n trees, and each tree has n nodes, so the space needed to store these trees is also proportional to O(n * C_n).

The recursion stack space will be proportional to the height of the recursion tree, which is O(n) since in the worst case we will make n nested recursive calls before hitting the base case. However, since the space required for the recursion stack is significantly smaller compared to the output space, it is often considered secondary.

Thus, the space complexity of the code is O(n * C_n) for storing the unique BSTs generated.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don’t know