GATE CSE 2021 Set 2 | Question: 16

Question

Consider a complete binary tree with $7$ nodes. Let $A$ denote the set of first $3$ elements obtained by performing Breadth-First Search $\text{(BFS)}$ starting from the root. Let $B$ denote the set of first $3$ elements obtained by performing Depth-First Search $\text{(DFS)}$ starting from the root.

The value of $\mid A-B \mid $ is _____________

Comments

…………………….

---

https://www.youtube.com/watch?v=jadnFei9wtw

Answer 1

Complete binary tree property has this property that every level until last is fully filled and last level is filled from left to right.

So, when we have a complete binary tree with $7$ nodes,

• $\text{level} _1$ has $1$ node ( root )
• $\text{level} _2$ has $2$ nodes.
• $\text{level} _3$ has $4$ nodes.

BFS goes level by level. So first three elements (say Set A) $=\text{level} _1$ nodes $(1)+ \text{ level} _2(2)$ nodes.

DFS is go by connected manner. So first three elements (say Set B ) $= \text{level} _1$ nodes (1)$+$ one node from $\text{level} _2$ nodes $+$ one node from $\text{level} _3$ nodes which is connected to the previously chosen $\text{level} _2$ node.

$A – B =$ the remaining node from the set of $\text{level} _2$ nodes.

$\implies |A – B| = 1.$

Comments

In |A-B| what is | | representing,

I think it is cardinality then why not n(A-B).

Someone clarify this doubt..

---

@asnr, both are same only, right ?

---

Yes buddy both are same.

---

| A-B| denotes length of set

Answer 2

The answer is $1$. See the image below.

$A=\{1,2,3\}$

and $B=\{1,2,4\}$ or $B=\{1,2,5\}$ or $B=\{1,3,6\}$ or $B=\{1,3,7\}$

for all cases, $|A-B|=1$

 

 

 

Comments

A={1,2,3} and B={1,2,4} or {1,2,5} or {1,3,6} or {1,3,7}
so  set diffrence Between A - B ={3 OR 4 OR 6 OR 7}
AND CARDINILTY IS |A-B| IS 1

---

A can also be 1,3,2  it is also bfs..is it?

---

@jugnu1337 Set is well defined collection of unordered distinct objects. 

Answer 3

Set A will contain = { root node , 2^nd level all node i.e 2 node}

Set B = { root node , one node from 2^nd level , one node from 3^rd level }

when we perform Set Difference operation :

A-B = one node from 2^nd level.

and cardinality will be

|A-B| = 1