edited by
12,965 views
49 votes
49 votes
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 __________
edited by

8 Answers

Best answer
49 votes
49 votes
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$
edited by
7 votes
7 votes
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.
3 votes
3 votes

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

3 votes
3 votes
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:

Related questions

34 votes
34 votes
4 answers
2
go_editor asked Sep 26, 2014
12,116 views
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...