FastPrepCount Distinct Binary Search Trees
Problems/Count Distinct Binary Search Trees

Count Distinct Binary Search Trees

C3.ai logoC3.ai● MediumFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2022 C3.ai software engineer report from campus recruiting lists a question it calls valid BSTs and says nothing else about it.

That name could mean checking one tree or counting trees. The report describes three question slots: an online test with a math or dynamic programming question and a palindrome question, and a call with one question that matches another item on its list. That leaves this question in the math slot, so this version counts trees. Here, you count the different trees for the values 1 to n, with n up to 35 so the answer fits in a 64-bit integer.

Our version is about 45% the same as the reported question.

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) → long

Examples

Example 1

n = 2return = 2

With 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 = 14

Pick 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 = 42

The 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

Interview reports that mention this question

  • C3.ai New Grad Interviews: 25 Experiences (Part 1 of 2)

C3.ai interview experiences

  • C3.ai FDE and Other New Grad Roles: 5 Experiences (Part 2 of 2)
  • C3.ai New Grad Forward Deployed Engineer Interview: 1 Experience
All C3.ai interview questionsSee C3.ai hiring insights
Saved
class Solution {
    public long countDistinctBSTs(int n) {
        // Write your code here.
    }
}
Checking account…