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:

  1. [2, [1, null, null], [3, null, null]]
  2. [1, null, [3, [2, null, null], null]]
  3. [3, [1, null, [2, null, null]], null]

In these trees:

  • The number in brackets is the value of the node.
  • null represents 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]]
Geek
Inputs

Arg 1:

1
Expected Output
[[1, null, null]]
Actual Output
Unique Binary Search Trees II [advanced] | Coding for Kids