MediumNo. 0096
Unique Binary Search Trees — LeetCode 96 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Binary Search Tree, Math, Dynamic Programming, Binary Tree
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example
- Input
- n = 3
- Output
- 5
Python solution
class Solution:
def numTrees(self, n: int) -> int:
f = [1] + [0] * n
for i in range(n + 1):
for j in range(i):
f[i] += f[j] * f[i - j - 1]
return f[n]Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 96. Unique Binary Search Trees is filed here because LeetCode tags it Tree, Binary Tree and Binary Search Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0095 | Unique Binary Search Trees II | Medium |
| 1569 | Number of Ways to Reorder Array to Get Same BST | Hard |
| 1373 | Maximum Sum BST in Binary Tree | Hard |
| 0124 | Binary Tree Maximum Path Sum | Hard |
| 0337 | House Robber III | Medium |
| 0894 | All Possible Full Binary Trees | Medium |
Frequently asked questions
- How hard is LeetCode 96. Unique Binary Search Trees?
LeetCode 96. Unique Binary Search Trees is rated Medium on LeetCode.
- What is the time complexity of LeetCode 96. Unique Binary Search Trees?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 96. Unique Binary Search Trees?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 96. Unique Binary Search Trees cover?
LeetCode 96. Unique Binary Search Trees is tagged Tree, Binary Search Tree, Math, Dynamic Programming and Binary Tree on LeetCode.