0

What is the number of binary search trees with 20 nodes with elements 1,2,3,...,20 such that the root of the tree is 12 and the root of the left sub tree is 7 ? a) 2634240 b) 1243561 c) 350016 d) 2642640

An explanation along with the answer would be helpful.

I have applied the Catalan number formula but the result is inappropriate from the options, so this is just to be sure.

Improve this question
5
  • Does the root of the left sub tree start with 7 or is the left tree itself 7 and only 7 Commented Sep 3, 2018 at 17:27
  • Can you show your application of the Catalan number formula? Then maybe we can indicate where you're going wrong. BTW, this may be more appropriate at math.stackexchange.com, unless you're expected to solve this by implementing some kind of brute force search. Commented Sep 3, 2018 at 17:31
  • root of the left sub tree is 7 and it has other elements as its children. Commented Sep 3, 2018 at 17:40
  • Cn= (2n)!/((n+1)!*n!) ; I used this formula Commented Sep 3, 2018 at 17:41
  • I have values on every node, there are in total 20 nodes, node with the value 12 is the root and node with the value 7 is the root of the left sub tree of node with value 12. Commented Sep 3, 2018 at 17:43

2 Answers 2

Reset to default
6

Using the Catalan numbers, counting full binary trees with n nodes, the answer would be d) 2642640 = 14 * 132 * 1430. That's the possibilities extending (sub)trees from each of our unknown subtrees.

 12 / \ 7 (8 nodes) / \ (6 nodes) (4 nodes)


Update:

As suggested by Mark Dickinson in the comments below, to clarify: the "nodes" mentioned in the diagram above and in the first statement are "internal" nodes, which we are arranging in all ways, whereas the nth Catalan number is counting full binary trees with n+1 leaf nodes. Binary trees with l leaf nodes have l - 1 internal nodes.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Nitpick: full binary trees isn't quite the right thing here; we're interested in general binary trees, so it may be worth explaining why (for example) C_6 is the appropriate thing to use for the number of 6-node trees. (In contrast, the number of full binary trees with 6 leaf nodes is C_5, which isn't what you want here, and the number of full binary trees with 6 total nodes is zero, since any full binary tree has an odd number of nodes.)
@MarkDickinson good point. However, "full binary trees" seems appropriate to me here, language borrowed from the description for this Catalan number application in Wikipedia. We are ignoring the leaves and only counting nodes (vertices) precisely because in "full binary trees," each vertex (node) has "either two children or no children," but in our case the trees are not full. Tree variations with 4 nodes, for example, have 5 leaves, which is why C_4 is appropriate for our "4 node" subtree.
Yes, exactly. I'm not disputing that C_6 * C_4 * C_8 is correct. I'm suggesting that the answer would be improved by including some extra explanation. We do want numbers of "full binary trees with n nodes", but the relevant values of n in that case are 13, 9 and 17, and it seems worth explaining where those values come from. Or, perhaps it's clearer to change to "full binary trees with n leaf nodes" for compatibility with Wikipedia, and then explain why we want to use n=7, n=5 and n=9 rather than n=6, n=4 and n=8, which is what your current answer implicitly suggests.
@MarkDickinson edited. Feel free to edit more if you think it can be improved.
1

  • This is basically wanting you to calculate number of unique BSTs' possible for a certain number of nodes.

  • In the end, final result will be multiplication of those numbers.

  • If this was in an exam, then you will have to do the multiplication. Otherwise, you can solve this programmatically using dynamic programming.

CODE:

class Solution { public int numTrees(int n) { if(n < 3) return n; int[] dp = new int[n+1]; dp[0] = 1; // just initializing it as base case dp[1] = 1;// meaning, only 1 possibility for 1 node. dp[2] = 2;// meaning, only 2 possibilities for 2 nodes. for(int i=3;i<=n;++i){ for(int j=1;j<=i;++j){ int nodes_on_left_of_j = j - 1; int nodes_on_right_of_j = i - j; dp[i] += dp[nodes_on_left_of_j] * dp[nodes_on_right_of_j]; // so multiply left side possibilites with right side possibilites for a particular root node. } } return dp[n]; } }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.