How many shapes can an order-matching tree take?

Question

A price-ordered matching engine can be organized as a binary search tree over n distinct price levels 1..n. Two trees are different if their shapes differ. Count how many structurally distinct BSTs exist over n levels.

n = 3  ->  5
n = 4  ->  14

Return the number of distinct BST shapes on n keys (the nth Catalan number), in O(n^2) time.

Accepted Answer

Pick which key is the root. If the root is the r-th smallest, then r-1 smaller keys form the left subtree and n-r larger keys form the right subtree, independently. So the count for n nodes sums, over every choice of root, the product of the left and right subtree counts. Let dp[m] be the number of shapes on m nodes with dp[0] = 1 (the empty tree is one shape). Tracing: dp[1]=1, dp[2]=2, dp[3] = dp[0]dp[2] + dp[1]dp[1] + dp[2]dp[0] = 2 + 1 + 2 = 5. Time O(n^2), space O(n). Edge cases: n = 0 returns 1 (the empty tree). These are the Catalan numbers, which also count balanced bracket strings an…

How many shapes can an order-matching tree take?

Your answer

More Coding questions