Construct Distinct Binary Search Trees (Medium) — Practice with Code Visualizer

You are given a positive integer n. Your task is to construct and return all structurally distinct binary search trees (BSTs) that contain exactly n nodes, where each node holds a unique integer value from 1 to n inclusive.

A binary search tree is a binary tree data structure where for every node:

All values in its left subtree are strictly less than the node's value.
All values in its right subtree are strictly greater than the node's value.
Both the left and right subtrees must also be valid binary search trees.

Two BSTs are considered structurally distinct if they have different arrangements of nodes, even if they contain the same set of values. This includes differences in which value appears at which position in the tree structure.

Return a collection of the root nodes of all such valid BSTs. The trees may be returned in any order.

Note: The output is displayed in level-order (BFS) serialization format, where null represents an absent child node. Trailing null values are omitted for brevity.

With n = 3, there are exactly 5 structurally unique BSTs containing values 1, 2, and 3. Each tree satisfies the BST property where left children are smaller and right children are larger than their parent nodes.

With only one node, there is exactly one possible BST: a single node containing the value 1.

With n = 2, there are exactly 2 structurally unique BSTs: one with 1 as root and 2 as its right child, and another with 2 as root and 1 as its left child.