Solution by I_am_Hokage


  • 0
    I

    Problem

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

    For example,
    Given n = 3, there are a total of 5 unique BST's.

    Clarification

    First of all, we are are counting NON-ISOMORPHIC binary trees. What that means?

    Non-formal definition of binary tree isomorphism:

    Two binary trees are isomorphic, if you can erase a number in each node and two resulting trees will have the same shape.

    Example

    Two binary trees T1 and T2 below are isomorphic, since we can erase all the values and two resulting binary trees will have the same shape(T').

    0_1518487524995_result.png

    Corollary

    Okey, finally we understand that since we are counting non-isomorphic binary trees we do not care about values in the nodes, we only know that there are n nodes in the tree.

    Intuition

    Let's denote B_n -- binary tree with exactly n nodes.

    Okay, first notice that our binary trees may differ in the size of the left and right subtree.

    How many nodes can be present in left subtree?

    We have one node as a root, so the number of the nodes in the left subtree is in range [0, n - 1]. From that we can derive the number of the nodes in the right subtree: if we have i nodes in the left subtree and one node as a root, then we have n - i - 1 nodes in the right subtree.

    We have to count all possible sizes of the left subtree. The size of the right subtree determines uniquely from the size of the left subtree.

    Also, for each left subtree with i nodes we can pick any from B_{n - i - 1} right subtrees, since they are completely independent.

    Finally, we derive a formula:

    B_n = Σ B_{i} * B_{n - i - 1}, i from 0 to n - 1.

    I have to say that B_n is called the n-th Catalan number. More information can be found here: https://en.wikipedia.org/wiki/Catalan_number


    Approach #1 Simple Recursion [Time Limit Exceeded]

    Intuition

    Just compute the Catalan numbers using the formula B_n = Σ B_{i} * B_{n - i - 1} recursively.

    Base case: B_0 = 1 and B_1 = 1.

    Java

    class Solution {
        public int catalan(int n) {
    
            if (n == 1 || n == 0) { //base case
                return 1;
            }
    
            int ans = 0;
            for (int i = 0; i < n; i++) { //sum over all i
                ans += catalan(i) * catalan(n - i - 1);
            }
    
            return ans;
        }
    
        public int numTrees(int n) {
            return catalan(n);
        }
    }
    

    Complexity Analysis

    • Time complexity : O(4^n).
      It can be proven that Catalan numbers grow exponentially.

    Formal proof can be found here:

    https://math.stackexchange.com/questions/1986247/asymptotic-approximation-of-catalan-numbers

    • Space complexity : O(1). No auxiliary data structures.

    Approach #2 Dynamic Programing [Accepted]

    Intuition

    Basically we use the same approach as above, but we apply memoization.

    Here dp[i] - number of structurally unique BST's with n nodes.

    We calculate dp[i] for i from 1 to n. In the inner loop we iterate over the size of the left subtree.

    Java

    class Solution {
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1; //base case
            for (int i = 1; i < n + 1; i++) { //evaluate all dp[i]
                for (int left = 0; left < i; left++) {
                  //loop over size of the left subtree
                    dp[i] += dp[left] * dp[i - left - 1];
                }
            }
            return dp[n];
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n^2). We have to evaluate the following sum: 1 + 2 + 3 + ... + n, but this is a geometric series so: 1 + 2 + 3 + ... + n = n * (n + 1) / 2.

    • Space complexity : O(n). Have to store an array.


    Approach #3 Using formula [Accepted]

    Intuition

    We can also use this fromula for Catalan numbers:

    B_n = (n + 2} * (n + 3) * (n + 4) * (n + n) / (2 * 3 * 4 * ... * n)

    Java

    class Solution {
        public int numTrees(int n) {
    
            double ans = 1;
    
            for (int i = 2; i < n + 1; i++) {
                ans *= (n + i);
                ans /= i;
            }
    
            //already for n = 19
            //it gives an error due to precision loss
    
            if (n == 19) {
                return (int) ans + 1;
            }
    
            return (int) ans;
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n). We iterate from 2 to n + 1.

    • Space complexity : O(1) No auxiliary data structures.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.