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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

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.

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

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

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

Not Sure What to Study? Take the 2-min Quiz：

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

95. Unique Binary Search Trees II

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Call the Main Function

Step 2: Loop Through Each Value as Root

Step 3: Recursively Generate Subtrees

Step 4: Construct Trees and Combine Subtrees

Step 5: Collect and Return the Results

Solution Implementation