Unique Binary Search Trees Ii

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) {
            return {};
        }
        return generateTrees(1, n);
    }
    
    vector<TreeNode*> generateTrees(int start, int end) {
        vector<TreeNode*> trees;
        if (start > end) {
            trees.push_back(nullptr);
            return trees;
        }
        
        for (int i = start; i <= end; ++i) {
            vector<TreeNode*> leftSubtrees = generateTrees(start, i - 1);
            vector<TreeNode*> rightSubtrees = generateTrees(i + 1, end);
            
            for (TreeNode* left : leftSubtrees) {
                for (TreeNode* right : rightSubtrees) {
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    trees.push_back(root);
                }
            }
        }
        
        return trees;
    }
};

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<TreeNode>();
        }
        return generateTrees(1, n);
    }
    
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if (start > end) {
            result.add(null);
            return result;
        }
        
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftSubtrees = generateTrees(start, i - 1);
            List<TreeNode> rightSubtrees = generateTrees(i + 1, end);
            
            for (TreeNode left : leftSubtrees) {
                for (TreeNode right : rightSubtrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.add(root);
                }
            }
        }
        
        return result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        if (n == 0) return new List<TreeNode>();
        return GenerateTrees(1, n);
    }
    
    public IList<TreeNode> GenerateTrees(int start, int end) {
        IList<TreeNode> res = new List<TreeNode>();
        
        if (start > end) {
            res.Add(null);
            return res;
        }
        
        for (int i = start; i <= end; i++) {
            IList<TreeNode> leftTree = GenerateTrees(start, i - 1);
            IList<TreeNode> rightTree = GenerateTrees(i + 1, end);
            
            foreach (var left in leftTree) {
                foreach (var right in rightTree) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.Add(root);
                }
            }
        }
        
        return res;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
    const generate = (start, end) => {
        if (start > end) return [null];
        
        const result = [];
        
        for (let i = start; i <= end; i++) {
            const leftTrees = generate(start, i - 1);
            const rightTrees = generate(i + 1, end);
            
            for (let left of leftTrees) {
                for (let right of rightTrees) {
                    const root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.push(root);
                }
            }
        }
        
        return result;
    };
    
    if (n === 0) return [];
    return generate(1, n);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number;
 *     left: TreeNode | null;
 *     right: TreeNode | null;
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.left = (left===undefined ? null : left);
 *         this.right = (right===undefined ? null : right);
 *     }
 * }
 */
function generateTrees(n: number): Array<TreeNode | null> {
    function generateTreesRecursive(start: number, end: number): Array<TreeNode | null> {
        const result: Array<TreeNode | null> = [];
        if (start > end) {
            result.push(null);
            return result;
        }
        
        for (let i = start; i <= end; i++) {
            const leftSubtrees = generateTreesRecursive(start, i - 1);
            const rightSubtrees = generateTreesRecursive(i + 1, end);
            
            for (let left of leftSubtrees) {
                for (let right of rightSubtrees) {
                    const root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.push(root);
                }
            }
        }
        
        return result;
    }
    
    if (n === 0) {
        return [];
    }
    
    return generateTreesRecursive(1, n);
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun generateTrees(n: Int): List<TreeNode?> {
        if (n == 0) return emptyList()
        return generateTrees(1, n)
    }
    
    fun generateTrees(start: Int, end: Int): List<TreeNode?> {
        val res = mutableListOf<TreeNode?>()
        if (start > end) {
            res.add(null)
            return res
        }
        for (i in start..end) {
            val leftSubtrees = generateTrees(start, i - 1)
            val rightSubtrees = generateTrees(i + 1, end)
            for (left in leftSubtrees) {
                for (right in rightSubtrees) {
                    val root = TreeNode(i)
                    root.left = left
                    root.right = right
                    res.add(root)
                }
            }
        }
        return res
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return []*TreeNode{}
    }
    return generateTreesDFS(1, n)
}

func generateTreesDFS(start, end int) []*TreeNode {
    var res []*TreeNode
    if start > end {
        res = append(res, nil)
        return res
    }

    for i := start; i <= end; i++ {
        leftTrees := generateTreesDFS(start, i-1)
        rightTrees := generateTreesDFS(i+1, end)
        for _, left := range leftTrees {
            for _, right := range rightTrees {
                root := &TreeNode{Val: i}
                root.Left = left
                root.Right = right
                res = append(res, root)
            }
        }
    }

    return res
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end

def generate_trees(n)
    def generate_trees_helper(start, last)
        return [nil] if start > last
        
        result = []
        (start..last).each do |i|
            left_trees = generate_trees_helper(start, i - 1)
            right_trees = generate_trees_helper(i + 1, last)
            
            left_trees.each do |left|
                right_trees.each do |right|
                    root = TreeNode.new(i)
                    root.left = left
                    root.right = right
                    result << root
                end
            end
        end
        result
    end
    
    generate_trees_helper(1, n)
end

To solve this coding challenge of generating all structurally unique Binary Search Trees (BSTs) with exactly \( n \) nodes containing unique values from 1 to \( n \), we can leverage a recursive approach. This approach will recursively construct BSTs by choosing each possible root and then generating left and right subtrees, ensuring all combinations are considered.

Explanation:

The task requires generating all possible unique BSTs with nodes numbered from 1 to \( n \). To approach this problem, we need to:

Decide a 'root' for our BST for each value from 1 to \( n \).
Recursively generate all possible left subtrees using values less than the chosen root.
Recursively generate all possible right subtrees using values greater than the chosen root.
Combine the left and right subtrees with the root to create a BST.
Store each unique combination generated in a result array.

For instance, if \( n \) is 3, valid BSTs could be created by choosing 1, 2, or 3 as the root. This recursive approach ensures every possible BST structure is considered.

Step-by-Step Explanation:

Define the Recursive Function:

Given start and end indices, if the start is greater than the end, it returns an array containing
null

since this represents an empty tree.

Iterate over All Possible Roots:

For each value \( i \) from
start

to
end

:

Generate all left subtrees with values from
start

to \( i-1 \).
Generate all right subtrees with values from \( i+1 \) to
end

.

Construct Trees for Each Root:

Combine each left subtree with each right subtree to form a new tree with the current root.
Append this newly formed tree to the result array.

Return the Result:

After iterating through all possible values for the root within the given range, return the result array containing all unique BSTs.

Detailed Steps in Pseudocode:

                                            
# Define a function to generate all unique BSTs
function generateUniqueBSTs(n):
# Helper function to generate BSTs for a given range
function generateTrees(start, end):
if start > end:
return [null]  # Base case: When start is greater than end, return an array with null

allTrees = []  # Initialize an array to store all unique BSTs

# Iterate through all values from start to end to use each value as root
for rootValue from start to end:
# Recursively generate all left subtrees of the root
leftSubtrees = generateTrees(start, rootValue - 1)
# Recursively generate all right subtrees of the root
rightSubtrees = generateTrees(rootValue + 1, end)

# Combine each left subtree with each right subtree
for left in leftSubtrees:  # Iterate through each left subtree
for right in rightSubtrees:  # Iterate through each right subtree
root = TreeNode(rootValue)  # Create a new tree node with the root value
root.left = left  # Attach the left subtree
root.right = right  # Attach the right subtree
allTrees.append(root)  # Append the new tree to the result array

return allTrees  # Return the array of all unique BSTs

# Edge case when n = 0, return an empty array
if n == 0:
return []

# Generate all unique BSTs for values from 1 to n
return generateTrees(1, n)

Initialization:

The main function
generateUniqueBSTs(n)

checks if \( n \) is zero. If true, it returns an empty list since there are no trees possible for zero nodes.

Recursive Generation:

The helper function
generateTrees(start, end)

handles the recursive generation of BSTs for a given range of values.
It returns
[null]

if
start

is greater than
end

indicating no valid tree structure.
For each value within the range as the root, it generates all possible left and right subtrees and combines them to form a new tree.

Tree Construction:

For each value serving as root, it constructs the tree by forming combinations of all left and right subtrees recursively and appends them to the
allTrees

array.

By following this detailed approach, we can ensure that all structurally unique BSTs within the given node range from 1 to \( n \) are generated.