TIFR CSE 2015 | Part B | Question: 4

Question

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.

• A. $2^{9}=512$
• B. $2^{4}.3^{2}.5.9=6480$
• C. $2^{3}.3.5.9=1080$
• D. $2^{4}=16$
• E. $2^{3}.3^{3}=216$

Comments

how to solve this question ?

Answer 1

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) 

Comments

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.

Answer 2

Based on concepts of Combination

Comments

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 .

Answer 3

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

Comments

Great so easy solution

---

This is not the right way. All permutations in the RST won’t satisfy the condition given in the question.

---

Yeah. Seems wrong to me too.

Answer 4

Tried to Simplify , Combinatorics concepts