Redirected
edited by
4,077 views
43 votes
43 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$
edited by

4 Answers

Best answer
59 votes
59 votes

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
21 votes
21 votes

Based on concepts of Combination

Based on concepts of Combination

7 votes
7 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
Answer:

Related questions

20 votes
20 votes
8 answers
2
makhdoom ghaya asked Dec 5, 2015
3,035 views
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 \time...