algoadvance

Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Clarifying Questions:

  1. Q: What should be the format of the output?
    • A: The output should be a list of TreeNode objects representing the root of each unique BST.
  2. Q: Should the BSTs be output in any particular order?
    • A: No, they can be returned in any order.
  3. Q: What if n is 0?
    • A: An empty list should be returned since no BST can be constructed.

Strategy:

  1. Understanding BST Property:
    • The value of the left subtree nodes should be less than the root node.
    • The value of the right subtree nodes should be greater than the root node.
  2. Recursive Construction:
    • Use recursion to construct trees.
    • For a given range of values (start to end):
      • Select each value in the range as a root.
      • Recursively generate all left subtrees with values less than the root.
      • Recursively generate all right subtrees with values greater than the root.
      • Combine each left subtree with each right subtree and the root to form a unique tree.
  3. Base Case:
    • If start > end, return [None] as there’s no valid tree in this range.
  4. TreeNode Class:
    • Create a simple TreeNode class to construct tree nodes.
  5. Efficiency Consideration:
    • Leverage memoization to store results of previously computed subproblems to avoid redundant calculations.

Code:

from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def generateTrees(n: int) -> List[Optional[TreeNode]]:
    if n == 0:
        return []
    
    def generate(start, end):
        if start > end:
            return [None]
        
        all_trees = []
        for i in range(start, end + 1):
            left_trees = generate(start, i - 1)
            right_trees = generate(i + 1, end)
            
            for l in left_trees:
                for r in right_trees:
                    current_tree = TreeNode(i)
                    current_tree.left = l
                    current_tree.right = r
                    all_trees.append(current_tree)
        
        return all_trees
    
    return generate(1, n)

# Example usage:
# Output will be trees in the form of TreeNode objects.
# To visualize, you might need additional helper functions.
for tree in generateTrees(3):
    print(tree)

Time Complexity:

The time complexity is a bit complex to determine due to the nature of the problem, but it’s generally considered to be catalan number related which is O((2^n) * n) to generate all unique BSTs. Here n is the given integer determining the number of unique nodes in the BST.

This problem fits within the dynamic programming and recursion domain with memoization to optimize the performance over the brute-force approach.

Feel free to test the function with the provided example or other values of n to ensure it works as expected.

Try our interview co-pilot at AlgoAdvance.com