Problem

Given n nodes, count distinct binary trees with distinct shapes.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: n = 3
Output: 5
Explanation: The five distinct binary trees for 3 nodes are:
1) All nodes as a left-skewed tree.
2) All nodes as a right-skewed tree.
3) Root with a left child and a left child's right child.
4) Root with a right child and a right child's left child.
5) Root with two children (one left and one right).

graph TD
    %% Tree 1: All as a left-skewed tree
    A1(" ") --> B1(" ")
    A1 ~~~ N11:::hidden
    B1(" ") --> C1(" ")
    B1 ~~~ N12:::hidden

    %% Tree 2: All as a right-skewed tree
    A2(" ") ~~~ N21:::hidden
    A2 --> B2(" ")
    B2(" ") ~~~ N22:::hidden
    B2 --> C2(" ")

    %% Tree 3: Root with a left child, and left child's left child
    A3(" ") --> B3(" ")
    A3 ~~~ N31:::hidden
    B3(" ") ~~~ N32:::hidden
    B3 --> C3(" ")

    %% Tree 4: Root with a left child, and left child's right child
    A4 ~~~ N41:::hidden
    A4(" ") --> B4(" ")
    B4(" ") --- C4(" ")
    B4 ~~~ N42:::hidden

    %% Tree 5: Root with two children (left and right)
    A5(" ") --> B5(" ")
    A5(" ") --> C5(" ")

classDef hidden display:none

Example 2

1
2
3

Input: n = 4
Output: 14
Explanation: Using the formula for Catalan numbers, the fourth Catalan number is 14.

Example 3

1
2
3
4
5

Input: n = 2
Output: 2
Explanation: The two distinct binary trees for 2 nodes are:
1) Root with a left child.
2) Root with a right child.

Solution

Method 1 - Using Maths and Catalan numbers

The number of distinct binary trees with n nodes, denoted as C(n), is determined by combining trees with a root, a left subtree of j nodes, and a right subtree of (n - 1) - j nodes for all possible values of j. This can be expressed as:

1

C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0)

The recursive formula is: $$ C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-i-1} $$

or alternatively, we can prove

$$ C_n = \frac{{2n!}}{{(n+1)!n!}} $$

The first few terms are

1
2
3
4
5

    C(0) = 1
    C(1) = C(0)C(0) = 1
    C(2) = C(0)C(1) + C(1)C(0) = 2
    C(3) = C(0)C(2) + C(1)C(1) + C(2)C(0) = 5
    C(4) = C(0)C(3) + C(1)C(2) + C(2)C(1) + C(3)C(0) = 14

Alternatively, it can be expressed recursively using: $$ C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-i-1} $$ Here’s the number of 8-node binary trees:

1
2
3

           1   16!    16×15×14×13×12×11×10
    C(8) = - × ---- = -------------------- = 13×11×10 = 1430
           9   8!8!      8×7×6×5×4×3×2×1

Approach

  1. Use a dynamic programming or iterative solution to compute Catalan numbers for n nodes. This avoids direct factorial computation and reduces complexity.
  2. Base case: (C_0 = 1) (An empty tree is one type of tree).
  3. Populate (C_n) iteratively for n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int countBinaryTrees(int n) {
        // Base case for 0 and 1
        if (n == 0 || n == 1) {
            return 1;
        }
        
        // Initialising the Catalan DP array
        int[] catalan = new int[n + 1];
        catalan[0] = 1;
        catalan[1] = 1;
        
        // Compute Catalan numbers iteratively
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                catalan[i] += catalan[j] * catalan[i - j - 1];
            }
        }
        
        // Return the nth Catalan number
        return catalan[n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countBinaryTrees(3)); // Output: 5
        System.out.println(sol.countBinaryTrees(4)); // Output: 14
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def count_binary_trees(self, n: int) -> int:
        # Base case for 0 and 1
        if n == 0 or n == 1:
            return 1
        
        # Initialising Catalan DP array
        catalan = [0] * (n + 1)
        catalan[0] = 1
        catalan[1] = 1
        
        # Compute Catalan numbers iteratively
        for i in range(2, n + 1):
            for j in range(i):
                catalan[i] += catalan[j] * catalan[i - j - 1]
        
        return catalan[n]

# Example usage
sol = Solution()
print(sol.count_binary_trees(3))  # Output: 5
print(sol.count_binary_trees(4))  # Output: 14

Complexity

  • ⏰ Time complexity: O(n^2). Calculating the nth Catalan number involves iterating up to n and performing calculations involving summing products.
  • 🧺 Space complexity: O(n). An array is used to store intermediate Catalan numbers to facilitate dynamic programming.

References