Katkat
Back

Count the Distinct Binary Search Tree Shapes for Keys 1 to n

AmazonSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

Count how many structurally different binary search trees can store the keys 1 through n exactly once, for n up to 19. It tests reasoning about how tree shapes decompose and counting combinatorial structures efficiently instead of building every tree.

Given an integer n, count how many structurally different binary search trees can hold the keys 1, 2, ..., n, with each key used exactly once.

Two trees count as different when their shapes differ. For a fixed set of keys, the search-tree ordering determines which key sits at each node of a given shape, so counting distinct trees is the same as counting distinct shapes.

Function Signature

def count_bst_shapes(n: int) -> int:

Rules

  • In a binary search tree, every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
  • Each tree must contain all n keys.
  • Return the number of distinct trees as an integer.

Constraints

  • 1 <= n <= 19
  • The largest answer, for n = 19, is 1,767,263,190, which fits in a signed 32-bit integer.

Examples

Example 1

Input: n = 3
Output: 5

The keys 1, 2 and 3 can be arranged into five different valid search trees.

Example 2

Input: n = 1
Output: 1

Example 3

Input: n = 4
Output: 14