Frog Position After T Seconds

Explore how to use breadth-first search on an undirected tree to calculate the probability that a frog reaches a target vertex after t seconds. Understand how to model random jumps to unvisited neighbors and handle cases with no available moves. This lesson helps you develop skills in probabilistic tree traversal relevant for coding interviews.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

You are given an undirected tree with n vertices labeled from $1$ to $n$ . A frog starts at vertex $1$ , at time $0$ , and makes one move per second.

At each step, the frog follows these rules:

Move to an unvisited neighbor:
If the frog has unvisited neighbors, it jumps to one of them, chosen uniformly at random (equal probability for each choice).
No revisiting:
The frog can not jump back to a vertex it has already visited.
Stay when stuck
The frog will keep jumping at its current vertex if there are no unvisited neighbors.

The tree is represented as an array of edges, where edges[i] = [ $a_i$ ...