# JavaScript DP solution that doesn't create right subtrees

• The key aspect of this DP solution is the binary tree property, where the highest node is always on the right.

So generate the tree T(level-1), and for each node N:

• Create a new TreeNode(level) and insert N on the left (any element on T(level-1) will always be less than level)
• For each right node R of N, create a new TreeNode(level) and insert between the current node and R. See the comments bellow for an illustration.
``````var copy = function(node) {
if (!node) return node;
let result = new TreeNode(node.val);
result.left = copy(node.left);
result.right = copy(node.right);
return result;
};

var generateTrees = function(n) {
let levels = [null, [new TreeNode(1)]];
for (let i = 2; i <= n; i++) {
let curLevel = levels[i] = [];
levels[i-1].forEach(item => {
// Every tree from generateTrees(n-1) is less
// than i, because this is a binary tree
let tmp = new TreeNode(i);
tmp.left = copy(item);
curLevel.push(tmp);

// Let's copy the current tree from generateTrees(n-1)
// 1
//   \
//     2
//       \
//         3
// Then for each level, let's insert a new node TreeNode(i) on the right,
// and move the old right to the left of the new node
// 1        1          1
//   \        \          \
//   (4)        2          2
//    /           \          \
//  2             (4)          3
//   \            /             \
//     3        3               (4)
//
// To avoid having to walk the right nodes every time (1 for the first level,
// 2 for the second level, and so on), we copy the source node and then modify
// it in place! So each iteration of this loop will generate a new solution.
let source = copy(item);
let node = source;
while (node) {
// Store the previous right subtree
let oldRight = node.right;

// The new right subtree starts with the current level node
node.right = new TreeNode(i);

// The old right subtree must be less than the current node,
// so we just put it on the left
node.right.left = oldRight;

// Save the tree as it's now, because it's a solution
curLevel.push(copy(source));

// Restore the old ordering
node.right = oldRight;

// And finally do the same for the (old) right subtree
node = node.right;
}
});
}
return levels[n];
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.