Log In
35 votes

First, consider the tree on the left.


On the right, the nine nodes of the tree have been assigned numbers  from the set $\left\{1, 2,\ldots,9\right\}$ so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree are less than all numbers in the other subtree). How many such assignments are possible? Hint: Fix a value for the root and ask what values can then appear in its left and right subtrees.

  1. $2^{9}=512$
  2. $2^{4}.3^{2}.5.9=6480$
  3. $2^{3}.3.5.9=1080$
  4. $2^{4}=16$
  5. $2^{3}.3^{3}=216$
in DS
edited by
how to solve this question ?

3 Answers

53 votes
Best answer

Option is B.

for every node -all numbers in one subtree are less than all numbers in the other subtree .

Firstly chose a value for root $- 9$ elements = $\mathbf{9}$ ways

Now, we hv $\mathbf{8}$ elements left - we hv to chose $\mathbf{3}$ for left subtree & $\mathbf{5}$ for right subtree.

Note: Here we can either chose $3$ nodes from beginning or end out of 8 elements we have ! $= \mathbf{2}$ ways

Now,we hv $3$ elements for left subtree & $5$ for right(Consider subtrees of subtree).

Left Subtree :

      whatever way we place , always one side is smaller than other {$6$ is smaller than $8$ in above example given in question} so, total ways $= \mathbf{3!} $ {three places put one by one} $=\mathbf{6}$ ways

Right Subtree :

Right subtree has two more sub-trees ,so that elements on one side should be smaller than other **

Steps :

  1. Select one element for root $=\mathbf{5}$ ways
  2. $4$ elements left ,Select one element for left $=\mathbf{2}$ ways {Either we can chose from left or right}
  3. $3$ elements left, for right subtree $=\mathbf{3!}$ ways $=\mathbf{6}$ ways

Total ways $= 9*2* 3! * 5 * 2 * 3! = 2^4* 3^2 * 5 * 9 = 6480 =$ B (Ans) 

edited by
i have a doubt regarding this as u said there are 9 ways to select root suppose i select 1 as root then how we construct left sub tree bcoz after selecting root as 1 there is no other elements smaller than 1 but we need exactely 3 elemants for left sub tree. plzz explain
all numbers in one subtree are less than all numbers in the other subtree


root is not a matter here

Here only we have to maintain "all numbers in one subtree are less than all numbers in the other subtree"

See here in question 7 is root.

That is not an issue for this question.

But all node of left subtree i.e.(6,9,8) must be greater than all node of right subtree (1,2,3,4,5)

nice explanation.....


What are 9 ways for root?m not getting  Shashi Kant Verma diagram.

All the 9 numbers can be there for the root.

Suppose 8 is chosen as root so from the left numbers 1 2 3 4 5 6 7 9 we have to fill the left and right trees such that left tree values are less than right or vice versa.

We can choose 123 or 679 for the left structure. If we choose  123 then 45679 have to be arranged on right structure.

Hope this helps.

 gari   if 1 choosen as a root?

Root can be 1 also.  If it is chosen as 1 then the left choices are 23456789. Now our aim is to assign the numbers in such a way that left subtree Values are less than right subtree values or vice versa . There is no relation with the root being less or more than any of the subtree.

Now from 23456789 either 234 or 789 as left. If 789 as left then 23456 to be assigned to right.

Fix a value for the root and ask what values can then appear in its left and right subtrees

supose if we choose 1 as root ,we can also think like this as in its left part (23456789) and at right nothing .it also satisfies condition.

we have to answer according to the tree structure given in the question.
Jst Superb ...
himanshu sir great explanation
Great explaination

Here we cannot change tree structure. right??

Means we cannot do $4$ nodes in left subtree and $4$ node in right subtree.

That is not possible, though it is not mentioned in question.

How to understand tree structure will remain same every time.

19 votes

Based on concepts of Combination

Based on concepts of Combination

Could You please explain it in detail.. ?? i am not getting 3 ways and 5 ways part, what are the numbers ??
why there are 2 ways and 2 ways in left subtree it should be 2 ways and one way respectively
It would be 2 and 2 ways because , we are not saying that it is a complete binary tree .
In complete binary tree , we have to fill the elements from left to right , correct ?
So if the question had mentioned that it is a complete binary tree , then there would had been 2 ways and 1 ways , because the left element would had been filled in 2 ways , then for filling the right element , there had been only 1 option .

But it is a binary tree , so we can fill the right element first also , we can fill the left element first also .
Hence it can be done in both the ways , that’s why it is 2 and 2 ways .
Correct me , if i am wrong .
5 votes
1 2 3 4 5 6 7 8 9                 no. of ways to select a root  = 9     ,   

after chosing root , choose right most 3 element fron this 1 to 9 series for left sub tree ( as elements of left sub tree should be greater than all elements of rignt subtree)   .   put thsese 3 elements in 3 nodes of left subtree in 3! ways

now we have left with 5 elements for right subtree . put these 5 elements in right subtree in 5! ways

so total trees ==  9 *5!*3!= 6480
Great so easy solution

Related questions

24 votes
3 answers
There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is. $2^{n}$ $n^{2}$ $\binom{n}{⌊n/2⌋}^{2}$ $\binom{2n}{n}$ None of the above.
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1.8k views
16 votes
7 answers
A $1 \times 1$ chessboard has one square, a $2 \times 2$ chessboard has five squares. Continuing along this fashion, what is the number of squares on the regular $8 \times 8$ chessboard? $64$ $65$ $204$ $144$ $256$
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1.3k views
20 votes
5 answers
Consider the following grammar (the start symbol is $E$) for generating expressions. $E \rightarrow T - E \mid T + E \mid T$ $T \rightarrow T * F \mid F$ $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$ With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?
asked Dec 8, 2015 in Compiler Design makhdoom ghaya 1.2k views
12 votes
3 answers
Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently). x:=1 cobegin x:= x + 1 || x:= x + 1 || x:= x + 1 coend Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of $x$ ... $\left \{2, 4 \right \}$ $\left \{ 2, 3 \right \}$ $\left \{2 \right \}$
asked Dec 8, 2015 in Operating System makhdoom ghaya 1k views