GATE CSE 2016 | Set 2 | Question: 11

Question

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{\text{th}}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________

Comments

what will be min & max in case of AVL tree ?
max will be 31 only ? what about min ? @ankitgupta.1729 

---

Should NOT these types of questions mention whether they are using 0-based or 1-based indexing?

---

they are asking for nth vertex, not the index fo that vertex, hope it helped:)

Answer 1

No of nodes at level $0$(root)  of tree $\Rightarrow  1$

No of nodes at level $1$ of tree $\Rightarrow  2$

No of nodes at level $2$ of tree $\Rightarrow 4$

No of nodes at level $3$ of tree $\Rightarrow 8$

No of nodes at level $4$ of tree $\Rightarrow 16$

Last node in level $4$th is the node we are looking for $\Rightarrow  1+2+4+8+16 \Rightarrow 31$

Comments

@Swami , minimum value  of '$n$' will be $5$ because for minimum '$n$' , binary tree will be left/right skewed or a binary tree where at each level , only one node will be present.

---

got it

---

maximum value of n is : 31
minimum value of n is : 5

 

Answer 2

The maximum number of nodes in a binary tree of height h are 2^(h+1) - 1. Here h=4, so maximum number of nodes will be 31.

Comments

Correct answer.

---

This is  one better than above

 

Answer 3

No of nodes at distance 0(root)  of tree =>1

No of nodes at distance 1 of tree =>2

No of nodes at distance 2 of tree =>4

No of nodes at distance 3 of tree =>8

No of nodes at distance 4 of tree =>16

Last node at distance 4 is the node we are looking for => 1+2+4+8+16 => 31

Comments

Bt this result should nt we apply when it is given the binary tree is complete I mean when it is given that all levels are full here bt it is not given in question that it is complete binary tree

---

Look at the question they were asking maximum value, if you will not make a complete binary tree then answer will be less than 31

---

Complete binary tree will give maximum value

Answer 4

BFS can also be used to find the depth of a binary tree.

The depth of node is defined as the number of edges from the root to the node.

They have given that $n^{th}$ vertex is found at depth 4,what is the maximum value of n?

At each depth, we can have maximum of $2^d$ node where d=current depth.

At, d=4, we would have $2^4=16$ nodes and assuming our tree is complete binary tree, The number of node till depth 3 are

$2^0+2^1+2^2+2^3=15$ nodes.

So, if root starts from as node 1, till depth 3, we would have node numbered 15.

At depth 4, we have 16 nodes and they will be numbered till 16+(16-1)=31. i.e. node numbered from 16 to 31.

So, maximum numbered node our BFS can see at depth 4 is 31.

Answer-31

Answer 5

It will help you to understand the problem

Comments

isn't this is 30th node of graph

---

30 is the index , but its the 31st value , like if u take 5 things in array index of 5th element will be 4 but that 4 index thing is the 5th thing of array

Answer 6

31 IS THE ANSWER