Number Of Binary Tree Topologies

Tags

Number Of Binary Tree Topologies

Category

Recursion

Difficulty

Very Hard

Problem Statement

Given a non-negative integer n, find the number of structurally distinct binary trees (topologies) that can be formed with exactly n nodes. Two trees are considered different if they have different structures, regardless of node values. This is equivalent to computing the nth Catalan number.

Intuition

A binary tree with n nodes has a root, a left subtree, and a right subtree. If the left subtree has k nodes, the right subtree must have n - 1 - k nodes (subtracting 1 for the root). The total number of trees is the sum over all valid splits of the product of left-subtree topologies and right-subtree topologies. This recurrence is the definition of the Catalan numbers: C(n) = sum(C(k) * C(n-1-k)) for k = 0 to n-1, with C(0) = 1.

Approach

  1. Base case: There is exactly 1 topology with 0 nodes (the empty tree).
  2. Recursive case: For n nodes, try every split where the left subtree gets k nodes (0 to n-1) and the right subtree gets n-1-k nodes. Multiply the counts and sum.
  3. Memoize or use bottom-up DP to avoid recomputation. The bottom-up approach builds an array where dp[i] holds the number of topologies for i nodes.
  4. Return dp[n].

Pseudocode

function numberOfBinaryTreeTopologies(n):
    dp = array of size n + 1, initialized to 0
    dp[0] = 1  # empty tree

    for i from 1 to n:
        for left from 0 to i - 1:
            right = i - 1 - left
            dp[i] += dp[left] * dp[right]

    return dp[n]

Recursive with memoization:

function numberOfBinaryTreeTopologies(n, memo = {0: 1}):
    if n in memo:
        return memo[n]

    count = 0
    for left from 0 to n - 1:
        right = n - 1 - left
        count += numberOfBinaryTreeTopologies(left, memo) *
                 numberOfBinaryTreeTopologies(right, memo)

    memo[n] = count
    return count

Time & Space Complexity

  • Time: O(n^2). The outer loop runs n times, and the inner loop runs up to n times for each value of i. Total work is 1 + 2 + ... + n = O(n^2).
  • Space: O(n) for the DP array.

Key Insights

  • This is a direct application of the Catalan number formula. The nth Catalan number grows exponentially: C(n) ~ 4^n / (n^(3/2) * sqrt(pi)).
  • The recurrence mirrors the structure of binary trees: choosing how many nodes go left vs. right.
  • Both the top-down (memoized recursion) and bottom-up (iterative DP) approaches have the same complexity, but the bottom-up approach avoids recursion stack overhead.
  • There is also a closed-form formula: C(n) = (2n)! / ((n+1)! * n!), which can be computed in O(n) time but may require big integer arithmetic for large n.
  • This count includes all binary trees, not just binary search trees. For BSTs with distinct keys, the count is the same because each topology corresponds to exactly one BST arrangement of 1..n.

Edge Cases

  • n = 0: return 1 (the empty tree is the single topology).
  • n = 1: return 1 (a single root node).
  • n = 2: return 2 (root with left child, or root with right child).
  • Large n: the result grows very fast; may need big integer support or modular arithmetic depending on constraints.

Linked mentions