NUHMAN.com

Introduction

LeetCode 95: Unique Binary Search Trees II asks you to generate all structurally unique binary search trees (BSTs) that store values from 1 to n. The problem requires generating all possible unique BSTs, which means that each tree must have a unique structure but can contain the same node values.

A binary search tree is defined as a tree where for each node:

• The left subtree contains only nodes with values less than the node’s value.
• The right subtree contains only nodes with values greater than the node’s value.

In this article, we'll explore a recursive approach to solving this problem using Go and understand how to efficiently generate all possible unique BSTs.

Problem Statement

Given an integer n, return all structurally unique BST's (binary search trees) that store values from 1 to n.

Example:

go

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]
]

In this example, the output consists of five different BSTs that can be created using the numbers 1, 2, and 3.

Approach:

Recursive Approach:

The core idea of this problem is based on recursion and divide-and-conquer. Here's the step-by-step approach:

1. Understanding the BST Structure: For a given root i (ranging from 1 to n), all values less than i will form the left subtree, and all values greater than i will form the right subtree. This means:

• The left subtree will contain values from 1 to i-1.
• The right subtree will contain values from i+1 to n.

1. Recursive Tree Generation:

• For each root i, recursively generate all unique BSTs for the left and right subtrees.
• Combine the left and right subtrees with the root node i.

1. Base Case:

• When the range of numbers is empty, return nil (no tree).
• When the range contains a single element, return a tree with that single element as the root.

1. Combination of Subtrees:

• For each possible left subtree and right subtree, combine them with the root node and generate a new tree.

Go Implementation

Recursive Solution

go

// 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 generateTree(1, n)
}

// Recursive function to generate trees from start to end
func generateTree(start, end int) []*TreeNode {
    var trees []*TreeNode

    // If there are no nodes to create, return nil
    if start > end {
        trees = append(trees, nil)
        return trees
    }

    // Try every number between start and end as the root
    for i := start; i <= end; i++ {
        // Recursively generate all possible left and right subtrees
        leftTrees := generateTree(start, i-1)
        rightTrees := generateTree(i+1, end)

        // Combine left and right subtrees with the current root i
        for _, left := range leftTrees {
            for _, right := range rightTrees {
                root := &TreeNode{Val: i}
                root.Left = left
                root.Right = right
                trees = append(trees, root)
            }
        }
    }

    return trees
}

Explanation:

1. TreeNode Definition:

• The TreeNode struct defines a node in the binary tree with the properties Val (node value), Left (left child), and Right (right child).

1. generateTrees Function:

• This function is the entry point, and it checks if n is zero. If n is zero, it returns an empty slice, meaning there are no trees to generate.
• Otherwise, it calls the recursive function generateTree with a range from 1 to n.

1. generateTree Function:

• The generateTree(start, end int) function generates all possible unique BSTs with values between start and end.
• If start is greater than end, it returns an empty tree (nil) to handle the case where there are no nodes to place.
• For each number i from start to end, we:
• Recursively generate all possible left subtrees (generateTree(start, i-1)).
• Recursively generate all possible right subtrees (generateTree(i+1, end)).
• Combine each left subtree with each right subtree and create a tree with i as the root.

1. Combination of Trees:

• For each combination of left and right subtrees, a new tree is created with the root i, and the left and right children are assigned to the left and right subtrees respectively.

1. Return the Result:

• Finally, the function returns the list of all unique BSTs generated for the given range.

Time and Space Complexity

MetricComplexityTime ComplexityO(4^n / n^(3/2))Space ComplexityO(n)

Where:

• Time Complexity: The time complexity arises from generating all unique BSTs. The number of unique BSTs that can be formed from n nodes is given by the Catalan number. The asymptotic time complexity is O(4^n / n^(3/2)).
• Space Complexity: The space complexity is O(n) due to the recursive stack space. Each recursive call stores a range of nodes, and in the worst case, the depth of recursion is n.

Edge Cases

1. n = 0:

• Input: n = 0
• Output: []
• Explanation: No trees can be generated with zero nodes, so we return an empty list.

1. n = 1:

• Input: n = 1
• Output: [1]
• Explanation: There is only one possible tree with a single node.

1. n = 2:

• Input: n = 2
• Output: [2,1]
• Explanation: There are two possible unique BSTs: one with 1 as the root and 2 as the right child, and another with 2 as the root and 1 as the left child.

1. Large n:

• As n increases, the number of unique BSTs grows rapidly. The recursive solution efficiently handles this by generating all unique combinations of left and right subtrees.

Conclusion

LeetCode 95: Unique Binary Search Trees II is a classic problem that tests your ability to generate all structurally unique binary search trees. The recursive approach provides a clear and intuitive solution that uses divide-and-conquer principles to generate all possible combinations of left and right subtrees for each root node.

The solution has an O(4^n / n^(3/2)) time complexity due to the Catalan number growth, and O(n) space complexity due to the recursion stack. This problem is a great exercise in recursion, tree construction, and dynamic programming.