How hard is LeetCode 95. Unique Binary Search Trees II?

LeetCode 95. Unique Binary Search Trees II is rated Medium on LeetCode.

What is the time complexity of LeetCode 95. Unique Binary Search Trees II?

The Python solution on this page runs in O(n \times G(n)).

What is the space complexity of LeetCode 95. Unique Binary Search Trees II?

The Python solution on this page uses O(n \times G(n)) auxiliary space.

What topics does LeetCode 95. Unique Binary Search Trees II cover?

LeetCode 95. Unique Binary Search Trees II is tagged Tree, Binary Search Tree, Dynamic Programming, Backtracking and Binary Tree on LeetCode.

Unique Binary Search Trees II — LeetCode 95 Python Solution

MediumTreeBinary Search TreeDynamic ProgrammingBacktrackingBinary Tree

Problem: #95
Pattern: Backtracking
Reading time: 4 min
Source: leetcode.com

The problem

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

Python solution

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def dfs(i: int, j: int) -> List[Optional[TreeNode]]:
            if i > j:
                return [None]
            ans = []
            for v in range(i, j + 1):
                left = dfs(i, v - 1)
                right = dfs(v + 1, j)
                for l in left:
                    for r in right:
                        ans.append(TreeNode(v, l, r))
            return ans

        return dfs(1, n)

Complexity

Measure	Complexity
Time	O(n \times G(n))
Space	O(n \times G(n)) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 95. Unique Binary Search Trees II is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 95. Unique Binary Search Trees II?: LeetCode 95. Unique Binary Search Trees II is rated Medium on LeetCode.
What is the time complexity of LeetCode 95. Unique Binary Search Trees II?: The Python solution on this page runs in O(n \times G(n)).
What is the space complexity of LeetCode 95. Unique Binary Search Trees II?: The Python solution on this page uses O(n \times G(n)) auxiliary space.
What topics does LeetCode 95. Unique Binary Search Trees II cover?: LeetCode 95. Unique Binary Search Trees II is tagged Tree, Binary Search Tree, Dynamic Programming, Backtracking and Binary Tree on LeetCode.