Unique Binary Search Trees II
Advanced
In this challenge, you will learn how to work with trees in a fun way. Your task is to generate all unique Binary Search Trees (BSTs) that store values 1 to n. A BST is a tree where the left-child node is always less than the parent node, and the right-child node is always more significant than the parent node.
Given an integer n, you will have to return all the unique BSTs that can be constructed with values from 1 to n. Each tree should be represented as a nested list where:
- The first element is the root value.
- The second element is the list representing the left subtree.
- The third element is the list representing the right subtree.
Example:
Imagine you have n = 3. You need to construct all BSTs that have the values 1, 2, and 3. Here is how you might represent some possible BSTs:
[2, [1, null, null], [3, null, null]][1, null, [3, [2, null, null], null]][3, [1, null, [2, null, null]], null]
In these trees:
- The number in brackets is the value of the node.
nullrepresents that there is no child node here.
Your function should return a list containing each unique BST, expressed as described above.
More Examples:
unique_bst_ii(1) # Output: [[1, null, null]] unique_bst_ii(2) # Output: [[1, null, [2, null, null]], [2, [1, null, null], null]] unique_bst_ii(3) # Output: [[1, null, [2, null, [3, null, null]]], [1, null, [3, [2, null, null], null]], [2, [1, null, null], [3, null, null]], [3, [1, null, [2, null, null]], null], [3, [2, [1, null, null], null], null]]
Inputs
Arg 1:
1Expected Output
[[1, null, null]]Actual Output