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$$-th vertex in this $$BFS$$ traversal, then the maximum possible value of $$n$$ is ___________.

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

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 adjacency matrix?