GATE Overflow Test Series | Mock GATE | Test 2 | Question: 49

Question

Suppose from the set of all possible distinct binary trees with $6$ nodes, one tree is chosen at random. What is the probability that this chosen tree is a heap (either min or max)?

• A. $5 / 33$
• B. $1 / 2376$
• C. $10 / 33$
• D. $1 / 4752$

Comments

if we assume unlabelled nodes then then ans is B

if we assume labelled nodes then ans is C

is “unlabelled nodes” the default mode?(Confused here)

Answer 1

For $n$ nodes the number of distinct binary trees is $^{2n}C_n*n!/(n+1)$. For $6$ nodes we have $95040$ trees possible. Also with $6$ nodes total $40$ heaps are possible ($20$ each for min and max heaps as shown at end).

Therefore required probability is $40/95040 = 1/2376.$

For a max-heap with $6$ nodes, we have $3$ levels. Total possible min-heaps $=\dfrac{6!}{6\times 3\times 2} = 20.$ (We have only one way to select the root.  The two subtrees of the root will have $3$ and $2$ elements. But instead of $3!$ and $2!$ possibilities as in a binary tree, in a max-heap, the number of possibilities will be just $2$ and $1$ respectively as the parent node gets fixed.

Comments

@mayank pathak  bro    if n is the total no of node   then formula of finding min/max heap is 

T(node) =  ( n-1  C  no of left node ) *  T(# right node) *T (#left node)

again use this same formula for T(# right node)  and  T (#left node)  in recursive mode

---

@shashankrustagi Distinct binary trees are given, not distinct nodes.If we assume unlabelled nodes then ans will be 10/33

---

if we assume unlabelled nodes then then ans is B

if we assume labelled nodes then ans is C

is “unlabelled nodes” the default mode?(Confused here)