Frog Position After T Seconds: BFS with Probability Tracking

You are given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts at vertex 1. At each second, the frog jumps to an unvisited vertex adjacent to its current vertex. If there are multiple unvisited neighbors, it jumps to each one with equal probability. If there are no unvisited neighbors, the frog stays in place. Given t seconds, return the probability that the frog is on vertex target after exactly t seconds.

This is LeetCode 1377: Frog Position After T Seconds, and it is one of the best problems for learning how to combine BFS traversal with probability propagation on a tree.

Why this problem matters

Many tree and graph problems ask you to find shortest paths or count nodes. This problem adds a twist: you need to track probability as you traverse. The frog does not choose where to go. It splits its probability equally among all unvisited children. This means each level of BFS is not just about visiting nodes, it is about dividing and carrying forward probabilities.

This pattern of propagating values through BFS levels shows up in problems involving expected values, random walks, and probability distributions on graphs. Once you see how probability flows through the tree here, you can apply the same idea anywhere a value needs to split among neighbors.

The key insight

The tree is rooted at vertex 1, and the frog moves downward (away from the root, since it never revisits a vertex). At each node, the probability is divided equally among the node's unvisited children. You can run BFS from vertex 1 and propagate probabilities level by level.

There are two critical edge cases to handle:

1. If the frog reaches the target before time t, it can only stay there if the target is a leaf (no unvisited neighbors). If the target has children, the frog must jump away, making the probability 0.
2. If the frog has not reached the target by time t, the answer is 0.

The algorithm:

1. Build an adjacency list from the edge list. Root the tree at vertex 1.
2. Run BFS from vertex 1, tracking the probability at each node.
3. At each step, divide a node's probability equally among its unvisited children.
4. After exactly t steps (or earlier if the target is a leaf), check the probability at the target.

The solution

from collections import deque, defaultdict

def frog_position(n: int, edges: list[list[int]], t: int, target: int) -> float:
    if n == 1:
        return 1.0 if target == 1 else 0.0

    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * (n + 1)
    visited[1] = True
    queue = deque([(1, 1.0)])

    for _ in range(t):
        for _ in range(len(queue)):
            node, prob = queue.popleft()
            children = [nb for nb in graph[node] if not visited[nb]]
            if children:
                child_prob = prob / len(children)
                for child in children:
                    visited[child] = True
                    queue.append((child, child_prob))
            else:
                queue.append((node, prob))

    for node, prob in queue:
        if node == target:
            return prob

    return 0.0

Let's walk through what each piece does.

The first check handles the trivial case: if the tree has only one node, the frog is always at vertex 1 with probability 1.

The adjacency list is built from the edge list. Since the tree is undirected, each edge is added in both directions. We use a visited array to prevent the frog from going back to its parent (simulating the "unvisited" constraint).

The BFS loop runs for exactly t steps. At each step, we process all nodes in the current level using the for _ in range(len(queue)) pattern. For each node, we find its unvisited children. If children exist, we split the probability equally among them and add them to the queue. If no children exist (the node is a leaf or all neighbors are visited), the frog stays in place, so we re-enqueue the node with the same probability.

After t steps, we scan the queue for the target node and return its probability. If the target is not in the queue, the frog cannot be there, so we return 0.

Visual walkthrough

Let's trace through a concrete example. The tree has 7 vertices, target = 7, and t = 2. Watch how probability divides at each BFS level.

Notice how the probability at vertex 7 stays at 1/3 from t=1 to t=2 because vertex 7 is a leaf. The frog has nowhere to go, so it sits there. If vertex 7 had children, the frog would have been forced to jump away, and the probability of being at vertex 7 at t=2 would be 0.

Complexity analysis

Time is O(n) where n is the number of vertices. Each vertex enters the BFS queue at most once. Building the adjacency list takes O(n) as well (a tree with n vertices has n-1 edges). The loop runs for at most t iterations, but since each node is processed at most once across all iterations, the total work is bounded by n.

Space is O(n) for the adjacency list, the visited array, and the BFS queue. In the worst case, a single level of the tree could hold O(n) nodes (a star graph), so the queue could contain up to n-1 entries.

The building blocks

1. BFS with value propagation

The pattern of carrying a value (here, probability) through BFS levels and splitting it among children:

queue = deque([(start, initial_value)])
for _ in range(steps):
    for _ in range(len(queue)):
        node, value = queue.popleft()
        children = get_unvisited_children(node)
        if children:
            for child in children:
                queue.append((child, value / len(children)))

This is standard BFS with one addition: each queue entry carries a value, and that value divides among the next level's nodes. You will see this pattern in problems involving expected values, signal propagation, and any scenario where a quantity distributes across a graph.

2. Leaf node detection in BFS

The pattern of detecting when a node has no unvisited children and handling it differently:

children = [nb for nb in graph[node] if not visited[nb]]
if children:
    for child in children:
        queue.append((child, prob / len(children)))
else:
    queue.append((node, prob))

This check separates "the frog must jump" from "the frog stays put." In tree problems, leaf detection often changes the logic. Here it determines whether probability persists at a node or flows to the next level. The same pattern appears in problems where you need to handle terminal states differently from intermediate ones.

3. Rooting an undirected tree with a visited array

The tree is given as an undirected edge list, but the frog only moves away from previously visited nodes. Using a visited array transforms the undirected tree into a directed one rooted at vertex 1:

visited = [False] * (n + 1)
visited[1] = True
children = [nb for nb in graph[node] if not visited[nb]]

This is simpler than explicitly rooting the tree. You skip the parent in the adjacency list by marking it as visited before processing its children. This pattern works for any problem where you need to traverse an undirected tree as if it were rooted.

Edge cases

Before submitting, think through these scenarios:

• n = 1, target = 1: The frog is already on the target. Return 1.0 regardless of t.
• Target is the root (target = 1) and t > 0: If vertex 1 has children, the frog must jump away at t=1. Return 0.0. If vertex 1 has no children (n=1), return 1.0.
• Target reached before t, but target is not a leaf: The frog was at the target at some step before t, but it had unvisited children and was forced to jump. Return 0.0.
• Target reached before t, and target is a leaf: The frog stays at the target for the remaining steps. Return the probability when it first arrived.
• Target unreachable within t steps: The target is deeper than t levels from the root. Return 0.0.
• Star graph (all nodes connected to root): All children of root are leaves. Probability of any child at t=1 is 1/(n-1). For t > 1, the frog stays on whatever leaf it landed on.

From understanding to recall

You have seen how BFS with probability propagation works: start at the root with probability 1, divide equally among children at each level, and handle leaf nodes by keeping the frog in place. The logic is clean, but the edge cases are where mistakes happen.

Do you re-enqueue leaf nodes or drop them? Do you check for the target at step t or after step t? What happens if the target is reached early but is not a leaf? These are the details that cost people under pressure, and they are not conceptual gaps. They are recall gaps.

Spaced repetition is how you close them. You practice writing the BFS loop with probability tracking, the leaf detection logic, and the termination check from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "probability on a tree" in a problem description, and the BFS template flows out without hesitation.

Related posts

• Number of Islands - The foundational BFS/DFS graph traversal problem that builds the skills this problem depends on
• Clone Graph - BFS traversal of a graph with node-level bookkeeping, similar to tracking probability at each node
• Course Schedule - Graph traversal with topological ordering, another pattern where BFS processes nodes level by level

CodeBricks breaks Frog Position After T Seconds into its BFS probability propagation, leaf detection, and tree rooting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree BFS problem shows up in your interview, you do not think about it. You just write it.