How many possible binary search trees can be made with the keys 1, 2, 3?123456Submit
Question
How many possible binary search trees can be made with the keys 1, 2, 3?123456Submit
Solution
The number of binary search trees that can be made with n distinct keys is given by the nth Catalan number. The formula for the nth Catalan number is:
Cn = (2n choose n) / (n + 1)
For n = 3, the number of possible binary search trees is:
C3 = (2*3 choose 3) / (3 + 1) = (6 choose 3) / 4 = 20 / 4 = 5
So, there are 5 possible binary search trees that can be made with the keys 1, 2, 3.
Similar Questions
The number of different binary search trees that can be made from two nodes that contain the key values 31 and 32 is 2.Group of answer choicesTrueFalse
The maximum number of levels that a binary search tree with 3 nodes can have is 2.Group of answer choicesTrueFalse
The number of different binary trees that can be made from two nodes that contain the key values 41 and 92 is 4.Group of answer choicesTrueFalse
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n. Example 1:Input: n = 3Output: 5Example 2:Input: n = 1Output: 1 Constraints:1 <= n <= 19
A binary search tree is generated by inserting following integers: 41, 30, 60, 25, 78, 90, 39, 50The number of nodes in the left subtree and right subtree of the root respectivelyA3, 4B5, 3C3, 5D4, 4
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.