Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices, it jumps randomly to one of them with the same probability. Otherwise, when the frog can not jump to any unvisited vertex, it jumps forever on the same vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi.
Return the probability that after t seconds the frog is on the vertex target. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4 Output: 0.16666666666666666 Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and then jumping with 1/2 probability to vertex 4 after second 2. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.
Example 2:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7 Output: 0.3333333333333333 Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.
Constraints:
1 <= n <= 100edges.length == n - 1edges[i].length == 21 <= ai, bi <= n1 <= t <= 501 <= target <= nProblem summary: Given an undirected tree consisting of n vertices numbered from 1 to n. A frog starts jumping from vertex 1. In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices, it jumps randomly to one of them with the same probability. Otherwise, when the frog can not jump to any unvisited vertex, it jumps forever on the same vertex. The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Return the probability that after t seconds the frog is on the vertex target. Answers within 10-5 of the actual answer will be accepted.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
7 [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]] 2 4
7 [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]] 1 7
longest-special-path)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1377: Frog Position After T Seconds
class Solution {
public double frogPosition(int n, int[][] edges, int t, int target) {
List<Integer>[] g = new List[n + 1];
Arrays.setAll(g, k -> new ArrayList<>());
for (var e : edges) {
int u = e[0], v = e[1];
g[u].add(v);
g[v].add(u);
}
Deque<Pair<Integer, Double>> q = new ArrayDeque<>();
q.offer(new Pair<>(1, 1.0));
boolean[] vis = new boolean[n + 1];
vis[1] = true;
for (; !q.isEmpty() && t >= 0; --t) {
for (int k = q.size(); k > 0; --k) {
var x = q.poll();
int u = x.getKey();
double p = x.getValue();
int cnt = g[u].size() - (u == 1 ? 0 : 1);
if (u == target) {
return cnt * t == 0 ? p : 0;
}
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.offer(new Pair<>(v, p / cnt));
}
}
}
}
return 0;
}
}
// Accepted solution for LeetCode #1377: Frog Position After T Seconds
func frogPosition(n int, edges [][]int, t int, target int) float64 {
g := make([][]int, n+1)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
type pair struct {
u int
p float64
}
q := []pair{{1, 1}}
vis := make([]bool, n+1)
vis[1] = true
for ; len(q) > 0 && t >= 0; t-- {
for k := len(q); k > 0; k-- {
u, p := q[0].u, q[0].p
q = q[1:]
cnt := len(g[u])
if u != 1 {
cnt--
}
if u == target {
if cnt*t == 0 {
return p
}
return 0
}
for _, v := range g[u] {
if !vis[v] {
vis[v] = true
q = append(q, pair{v, p / float64(cnt)})
}
}
}
}
return 0
}
# Accepted solution for LeetCode #1377: Frog Position After T Seconds
class Solution:
def frogPosition(
self, n: int, edges: List[List[int]], t: int, target: int
) -> float:
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
q = deque([(1, 1.0)])
vis = [False] * (n + 1)
vis[1] = True
while q and t >= 0:
for _ in range(len(q)):
u, p = q.popleft()
cnt = len(g[u]) - int(u != 1)
if u == target:
return p if cnt * t == 0 else 0
for v in g[u]:
if not vis[v]:
vis[v] = True
q.append((v, p / cnt))
t -= 1
return 0
// Accepted solution for LeetCode #1377: Frog Position After T Seconds
struct Solution;
impl Solution {
fn frog_position(n: i32, edges: Vec<Vec<i32>>, t: i32, target: i32) -> f64 {
let n = n as usize;
let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
let mut prob: Vec<f64> = vec![0.0; n];
prob[0] = 1.0;
for e in edges {
let u = e[0] as usize - 1;
let v = e[1] as usize - 1;
adj[u].push(v);
adj[v].push(u);
}
Self::dfs(0, 0, t, &mut prob, &adj);
prob[target as usize - 1]
}
fn dfs(u: usize, prev: usize, t: i32, prob: &mut Vec<f64>, adj: &[Vec<usize>]) {
let size = adj[u].len() - if u == prev { 0 } else { 1 };
if size == 0 || t == 0 {
return;
}
let p = prob[u];
for &v in &adj[u] {
if v != prev {
prob[v] += p / size as f64;
Self::dfs(v, u, t - 1, prob, adj);
}
}
prob[u] = 0.0;
}
}
#[test]
fn test() {
use assert_approx_eq::assert_approx_eq;
let n = 7;
let edges = vec_vec_i32![[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]];
let t = 2;
let target = 4;
let res = 0.16666666666666666;
assert_approx_eq!(Solution::frog_position(n, edges, t, target), res);
let n = 7;
let edges = vec_vec_i32![[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]];
let t = 1;
let target = 7;
let res = 0.3333333333333333;
assert_approx_eq!(Solution::frog_position(n, edges, t, target), res);
let n = 7;
let edges = vec_vec_i32![[1, 2], [1, 3], [1, 7], [2, 4], [2, 6], [3, 5]];
let t = 20;
let target = 6;
let res = 0.16666666666666666;
assert_approx_eq!(Solution::frog_position(n, edges, t, target), res);
}
// Accepted solution for LeetCode #1377: Frog Position After T Seconds
function frogPosition(n: number, edges: number[][], t: number, target: number): number {
const g: number[][] = Array.from({ length: n + 1 }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const q: number[][] = [[1, 1]];
const vis: boolean[] = Array.from({ length: n + 1 }, () => false);
vis[1] = true;
for (; q.length > 0 && t >= 0; --t) {
for (let k = q.length; k > 0; --k) {
const [u, p] = q.shift()!;
const cnt = g[u].length - (u === 1 ? 0 : 1);
if (u === target) {
return cnt * t === 0 ? p : 0;
}
for (const v of g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push([v, p / cnt]);
}
}
}
}
return 0;
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.