Unique Binary Search Trees1 min read

0
58
Word Search II

Unique Binary Search Trees Solution

Question

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example

Input: 3 
Output: 5 
Explanation: Given n = 3, there are a total of 5 unique BST's:
1    3   3   2   1 
\    /  /   / \   \ 
 3  2  1   1   3   2 
/  /    \           \ 
2  1     2           3

Solution

Solution in C++

Program

class Solution {
public:
    int numTrees(int n) {
        int dp[n+1];
        fill_n(dp,n+1,0);
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i] = dp[i] + (dp[i-j] * dp[j-1]);
            }
        }
        return dp[n];
    }
};

See Day 23 – Count Complete Tree Nodes

LEAVE A REPLY

Please enter your comment!
Please enter your name here