Count Distinct Binary Search Trees
Updated
Problem statement
Given an integer n, return how many structurally different binary search trees can store exactly the values 1 to n, each value once.
In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.
Trees with different shapes count as different. Once the shape is fixed, the order rule decides where each value goes, so each shape gives exactly one tree. For n <= 35, the answer fits in a signed 64-bit integer.
Function
countDistinctBSTs(n: int) → longExamples
Example 1
n = 2return = 2With the values 1 and 2, either value can be the root. If 1 is the root, 2 is its right child. If 2 is the root, 1 is its left child. That gives 2 different trees.
Example 2
n = 4return = 14Pick each value as the root in turn. The smaller values must form the left subtree and the larger values the right subtree, and those two parts can be shaped independently. There are 1, 1, 2 and 5 possible trees for 0, 1, 2 and 3 values (the empty tree counts once), so the counts are: root 1: 1 * 5 = 5, root 2: 1 * 2 = 2, root 3: 2 * 1 = 2, root 4: 5 * 1 = 5. The total is 5 + 2 + 2 + 5 = 14.
Example 3
n = 5return = 42The same split for 5 values gives 14 + 5 + 4 + 5 + 14 = 42: root 1 leaves 4 values on the right (14 ways), root 2 gives 1 * 5, root 3 gives 2 * 2, root 4 gives 5 * 1, and root 5 gives 14.
Constraints
1 <= n <= 35
More C3.ai interview questions
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Largest Square Sub-Grid Within a Sum LimitOA · Seen Jan 2023
- Prefix Scores With the Running MaximumOA · Seen Jan 2023
- Tree Node With Maximum BeautyOA · Seen Nov 2022
- Count Vowel Strings With Follow RulesOA · Seen Apr 2022
- Photo Album Insert OrderOA · Seen Apr 2022
- Sort by Frequency, Then ValueOA · Seen Apr 2022
- Count Palindromic Subsequences of Length KOA · Seen Mar 2022
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
Similar questions at other companies
- Stable Workload Redistribution TreesTower Research Capital · OA
- Frog Paths Without Long RunsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions
- Find Encrypted NumberAmazon · OA
- Valid PasswordsMathWorks · OAMathWorks interview questions
- Coloring HousesSnowflake · OASnowflake interview questions
- Find Maximum Number of StringsMoveworks · OAMoveworks interview questions
- Count Nondecreasing Digit-Sum ArraysMicrosoft · OAMicrosoft interview questions
- Count Valid A-B-C Sequences Under a Modulo-Four RuleInfosys · OAInfosys interview questions
- Count Permutations Without Three Equal Parities in a RowGoogle · OAGoogle interview questions