Frog Position After T Seconds - Video Solutions

Problem Overview: You are given an undirected tree with n nodes. A frog starts at node 1 and every second jumps to one of its unvisited neighbors with equal probability. After t seconds, compute the probability that the frog is at the target node. The challenge is modeling the probability flow across the tree while respecting the rule that the frog cannot revisit nodes.

Approach 1: Recursive DFS with Probability Tracking (O(n) time, O(n) space)

This approach treats the tree as a probability flow problem. Build an adjacency list and run a DFS from node 1. At each node, count how many unvisited neighbors are available. If the frog has k choices, each branch receives probability current_prob / k. The recursion continues until either the time reaches t or the frog reaches a leaf. Special handling is required when the frog reaches the target before time runs out: the probability is valid only if the node has no unvisited neighbors left (the frog stays put). DFS works well because it naturally follows paths while carrying probability and time as parameters. The traversal touches each node once, giving O(n) time and O(n) recursion stack space. This approach fits naturally with problems involving trees and probabilistic branching, similar to many Depth-First Search patterns.

Approach 2: BFS with Level Tracking (O(n) time, O(n) space)

A BFS simulation models the frog’s movement second by second. Start with a queue containing (node=1, probability=1.0). Each BFS level represents one second of time. When processing a node, compute how many unvisited neighbors it has and distribute the probability evenly among them before pushing them into the queue. Mark nodes as visited to enforce the rule that the frog never jumps backward. If a node has no unvisited neighbors, its probability remains at that node for the remaining time steps. BFS is often easier to reason about because the queue already aligns with time progression. Each edge is processed at most once, resulting in O(n) time and O(n) queue storage. This technique is common when working with Breadth-First Search on a graph where state evolves per level.

Recommended for interviews: Both DFS and BFS achieve optimal O(n) complexity. Interviewers usually expect the DFS probability propagation because it shows strong reasoning about tree traversal and branching probabilities. BFS is equally valid and sometimes easier to implement without recursion. Showing both approaches demonstrates that you understand tree traversal patterns and how probability flows through a graph structure.