Can some one help with this problem.
1 Like
I am also searching for the help because i got wrong answer verdict. may be someone can help me with this. what i did was calculate number of values present at every level and result is the product of factorials of those values. submission
I have seen the statement, I have not tried submitting this, so, correct me if I’m wrong, this is what I was able to come up with:
The first thing that you need to observe is that, the root of the tree must be the first number to be inserted, because, if it isn’t, then it will not be the root of the tree.
So, the number of ways will depend on the number of ways you can insert the nodes into the two children. Let’s suppose that there is only one ordering for each of the child nodes. Suppose that there are three numbers each in the left and the right subtrees, say, {1,2,3} in the left and {5,6,7} in the right. In a combination of these, any ordering that maintains the relative ordering of the two lists is valid.
I’ll explain with an example : {5,1,2,6,7,3}, {1,5,2,3,6,7} etc, as you can see, in both these combinations, the relative order is still maintained ie., 1 comes before 2, 2 comes before 3 and so on. We need to count the number of orderings that will satisfy this property.
You can see that each of these orderings will be of this form (for the above example) _ 1 _ 2 _ 3 _ , where, each of the ‘_’ can be filled by zero or more numbers from the second list. Since the order in which the numbers will be added to these spaces is fixed, the only thing that matters is the count of the numbers that will go in each of those spaces. If there are n1 numbers in the first list and n2 numbers in the second list, then you will have (n1+n2)C(n1) ways of doing this.
Also, we assumed that each of the children have only 1 valid ordering. If this is not the case, and there are w1,w2 ways for both of them respectively, then you will have w1w2(n1+n2)C(n1) ways. Let me know in the comments if there is something that you don’t understand or if you find some mistake in my approach.
1 Like