in DS retagged by
10,987 views
14 votes
14 votes
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 _____________
in DS retagged by
by
11.0k views

2 Comments

…………………….

5
5
0
0

3 Answers

14 votes
14 votes
Best answer

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.$

selected by

4 Comments

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

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

Someone clarify this doubt..

0
0
@asnr, both are same only, right ?
1
1
Yes buddy both are same.
1
1
| A-B| denotes length of set
0
0
21 votes
21 votes

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$

 

 

 

edited by

5 Comments

But in the question its written as complete binary tree not bst numbers can be in any order range .
0
0
Yes, these numbers could be anything, we can keep them as $a,b,c$ etc as well but the answer would not change.
0
0
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
2
2
A can also be 1,3,2  it is also bfs..is it?
0
0

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

1
1
2 votes
2 votes

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

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

when we perform Set Difference operation :

A-B = one node from 2nd level.

and cardinality will be

|A-B| = 1

Answer:

Related questions