96. Unique Binary Search Trees

Problem¶

Given values \(1\) through \(n\), return the number of structurally distinct binary search trees containing every value exactly once.

n = 3
root contributions = [2, 1, 2]
output = 2 + 1 + 2 = 5

Key trick¶

Choose each value as the root: if its left subtree has left nodes, its right subtree has nodes - 1 - left nodes, giving dp[left] * dp[right] combinations.

Trap¶

• Forgetting dp[0] = 1, which represents one valid empty subtree.
• Adding left and right possibilities instead of multiplying them.
• Assuming each smaller tree has the same number of valid insertion positions.

Why is it interesting?¶

It turns a structural counting problem into the Catalan recurrence by splitting each tree at its root.

Python solution¶

class Solution:
    def numTrees(self, n: int) -> int:
        # dp[nodes] is the number of unique BSTs containing that many nodes.
        dp = [0] * (n + 1)
        dp[0] = 1

        for nodes in range(1, n + 1):
            for left in range(nodes):
                right = nodes - 1 - left
                dp[nodes] += dp[left] * dp[right]

        return dp[n]

Time complexity: \(O(n^2)\).

Space complexity: \(O(n)\).

Comment on my solution¶

Your recurrence simplifies to dp[i] = i * dp[i - 1], so it computes \(i!\) rather than the Catalan numbers.

The new maximum cannot be counted using a fixed number of insertion positions per previous shape. Instead, choosing a root creates two independent subtree choices, whose counts must be multiplied and then summed over every possible split.

# Ideas:
# - dp[i] number of structuraly unique BSTs with i nodes
#   - how to compute d[i] from d[i-1] ???
# - Any new node is superior to all previous node
#   - so it can be put at the end of inorder traversal as right node
#     - count is dp[i - 1]
#   - or anywhere before (still regarding inorder)
#     - the node that comes after become part of its subtree
#     - count is (i - 1) * dp[i - 1]
#   - this is wrong.  There's something I don't see clearly.

# WRONG
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 1]
        return dp[n]

Solution().numTrees(1)
Solution().numTrees(2)
Solution().numTrees(3)

Extra¶

Relation between BST shapes and unlabeled binary-tree shapes¶

The BST property "left leaves inferior to node and right leaves superior" doesn't seemed to be used. The claim "if its left subtree has left nodes, its right subtree has nodes - 1 - left nodes" seems to work for any tree with nodes nodes. Am I missing something?

You are noticing a real connection: the number of BST shapes equals the number of ordinary unlabeled binary-tree shapes, both given by the Catalan numbers.

The BST property is hidden in why subtree sizes determine the values uniquely.

For values 1..n, if the root is k:

• Its left subtree must contain exactly 1..k-1, so it has k-1 nodes.
• Its right subtree must contain exactly k+1..n, so it has n-k nodes.
• The left and right subtree structures can be chosen independently.

Therefore:

Equivalently, if the left subtree has left nodes, the BST property forces the root to be the (left + 1)-th smallest value. There is no choice about which values belong to either subtree.

For example, with values 1, 2, 3, consider this shape:

    ?
   / \
  ?   ?

The BST property forces its labeling:

    2
   / \
  1   3

Without the BST property, the same shape could have any of the \(3!\) labelings.

So the statement

The left subtree has left nodes and the right subtree has nodes - 1 - left nodes.

is true for every binary tree. However, the recurrence without additional factors works here because:

• BST ordering uniquely assigns sorted values to any given shape.
• Every binary-tree shape has exactly one valid BST labeling with 1..n.

Another way to see it is that an inorder traversal of a BST must produce:

1, 2, ..., n

Thus, once a tree shape is chosen, assigning these values in inorder produces exactly one BST. That is the bijection between BST shapes and unlabeled binary-tree shapes.

Ok. So, for a given n, the number of binary-tree shapes for trees with n nodes is independent of the ordering of the nodes, and so the ordering property of BSTs is not needed to deduce the recurrence formula. Am I right?

Yes.

The recurrence counts unlabeled binary-tree shapes:

The BST property is not needed to derive it. It is needed only to show that every shape corresponds to exactly one BST over values 1..n, obtained by assigning the values in inorder.