Java | Recursive Solution - 88% fast
\npublic class Solution {\n    private Map<TreeNode, Integer> map;\n    private int mod = 1000000007;\n    \n    public Solution() {\n        map = new HashMap<
```  \npublic class Solution {\n    private Map<TreeNode, Integer> map;\n    private int mod = 1000000007;\n    \n    public Solution() {\n        map = new HashMap<>();\n    }\n    class TreeNode {\n        public int val;\n        public TreeNode left;\n        public TreeNode right;\n\n        public TreeNode(int val) {\n            this.val = val;\n            left = null;\n            right = null;\n        }\n    }\n\n    public int numOfWays(int[] nums) {\n        TreeNode root = buildTree(nums);\n        return (int) (numOfWays(root) % mod) - 1;\n    }\n    \n    private long numOfWays(TreeNode node) {\n        if (node == null)\n            return 1;\n        int n = numOfNodes(node.left);\n        int m = numOfNodes(node.right);\n        \n        return ((((binomialCoeff(n + m, n) % mod) * numOfWays(node.left)) % mod) * numOfWays(node.right)) % mod;\n    }\n\n\t// calulate the number of descendants of this node including the node itself\n    private int numOfNodes(TreeNode node) {\n\t\t// dp to decrease the runtime\n        if (map.containsKey(node))\n            return map.get(node);\n        if (node == null) \n            return 0;\n        \n        int num = 1 + numOfNodes(node.left) + numOfNodes(node.right);\n        map.put(node, num);\n        return num;\n    }\n    \n\t// method to calculate the value of nCk\n    private int binomialCoeff(int n, int k) {\n        int[] c = new int[k + 1];\n        c[0] = 1;\n        \n        for (int i = 1; i <= n; i++) {\n            for (int j = Math.min(i, k); j > 0; j--) \n                c[j] = (c[j] + c[j - 1]) % mod;\n        }\n        return c[k] % mod;\n    }\n\n  \n    private TreeNode buildTree(int[] nums) {\n        TreeNode tree = null;\n        for (int num : nums)\n            tree = insert(tree, num);\n        return tree;\n    }\n\n    private TreeNode insert(TreeNode root, int val) {\n        if (root == null)\n            return new TreeNode(val);\n\n        if (val < root.val)\n            root.left = insert(root.left, val);\n        else if (val > root.val)\n            root.right = insert(root.right, val);\n\n        return root;\n    }\n\n}\n\n```
['Dynamic Programming', 'Binary Search Tree', 'Combinatorics', 'Java']