DP #43. Count Binary Tree Preorder sequence - mbhushan/dynpro GitHub Wiki

(43). Count binary tree.

Given a preorder sequence how many unique trees can be created.

Solution is catalan number. Number of tree is exactly same
as number of unique BST create with array of size n.

    public int countBinaryTree(int n) {

        if (n == 0 || n == 1) {
            return 1;
        }

        int [] T = new int[n+1];
        T[0] = 1;
        T[1] = 1;

        for (int i=2; i<=n; i++) {
            for (int j=0; j<i; j++) {
                T[i] += (T[j] * T[i-j-1]);
            }
        }

        return T[n];
    }

• Time complexity: O(n^2)
• Space complexity: O(n)