Unique Binary Search Trees — LeetCode 96 Python Solution
MediumTreeBinary Search TreeMathDynamic ProgrammingBinary Tree
- Problem
- #96
- Pattern
- Tree Traversal
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
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
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.