Unique Binary Search Trees
Last updated
Was this helpful?
Last updated
Was this helpful?
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
To answer how many unique BSTs, need to know how to build a BST first. The approach could be recursively construct left and right sub-trees (:
For a sorted sequence: 1 ... n
, construct BST:
select i
in the sequence
sub sequence 1 ... (i - 1)
on the left
sub sequence (i+1) ... n
on the right
construct the sub tree from the sub sequence recursively
Dynamic Programming
The two functions (state):
G(n)
- the number of unique BST for a sequence of length n
.
F(i, n)
- the number of unique BST, where the number i is served as the root of BST (1 ≤ i ≤ n)
.
Where
G(n) = SUM(F(i, n)) over i = 1, ..., n.
And
F (i, n) = G(i - 1) * G(n - i)
Thus
G(n) = SUM(G(i - 1) * G(n - i)) over i = 1, ..., n
Initial State:
G(0) = 1, G(1) = 1
Final answer
G(n)
is actually the desired function we need in order to solve the problem.
DP - O(n^2) time, O(n) space (0ms, 100% AC)
Math - Catalan Number
LeetCode solution (
Binary Search Tree Data Structure: