LeetCode #3585 — HARD

Find Weighted Median Node in Tree

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode

The Problem

Problem Statement

You are given an integer n and an undirected, weighted tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [u_i, v_i, w_i] indicates an edge from node u_i to v_i with weight w_i.

The weighted median node is defined as the first node x on the path from u_i to v_i such that the sum of edge weights from u_i to x is greater than or equal to half of the total path weight.

You are given a 2D integer array queries. For each queries[j] = [u_j, v_j], determine the weighted median node along the path from u_j to v_j.

Return an array ans, where ans[j] is the node index of the weighted median for queries[j].

Example 1:

Input: n = 2, edges = [[0,1,7]], queries = [[1,0],[0,1]]

Output: [0,1]

Explanation:

Query	Path	Edge Weights	Total Path Weight	Half	Explanation	Answer
`[1, 0]`	`1 → 0`	`[7]`	7	3.5	Sum from `1 → 0 = 7 >= 3.5`, median is node 0.	0
`[0, 1]`	`0 → 1`	`[7]`	7	3.5	Sum from `0 → 1 = 7 >= 3.5`, median is node 1.	1

Example 2:

Input: n = 3, edges = [[0,1,2],[2,0,4]], queries = [[0,1],[2,0],[1,2]]

Output: [1,0,2]

Explanation:

Query	Path	Edge Weights	Total Path Weight	Half	Explanation	Answer
`[0, 1]`	`0 → 1`	`[2]`	2	1	Sum from `0 → 1 = 2 >= 1`, median is node 1.	1
`[2, 0]`	`2 → 0`	`[4]`	4	2	Sum from `2 → 0 = 4 >= 2`, median is node 0.	0
`[1, 2]`	`1 → 0 → 2`	`[2, 4]`	6	3	Sum from `1 → 0 = 2 < 3`. Sum from `1 → 2 = 2 + 4 = 6 >= 3`, median is node 2.	2

Example 3:

Input: n = 5, edges = [[0,1,2],[0,2,5],[1,3,1],[2,4,3]], queries = [[3,4],[1,2]]

Output: [2,2]

Explanation:

Query	Path	Edge Weights	Total Path Weight	Half	Explanation	Answer
`[3, 4]`	`3 → 1 → 0 → 2 → 4`	`[1, 2, 5, 3]`	11	5.5	Sum from `3 → 1 = 1 < 5.5`. Sum from `3 → 0 = 1 + 2 = 3 < 5.5`. Sum from `3 → 2 = 1 + 2 + 5 = 8 >= 5.5`, median is node 2.	2
`[1, 2]`	`1 → 0 → 2`	`[2, 5]`	7	3.5	Sum from `1 → 0 = 2 < 3.5`. Sum from `1 → 2 = 2 + 5 = 7 >= 3.5`, median is node 2.	2

Constraints:

2 <= n <= 10⁵
edges.length == n - 1
edges[i] == [u_i, v_i, w_i]
0 <= u_i, v_i < n
1 <= w_i <= 10⁹
1 <= queries.length <= 10⁵
queries[j] == [u_j, v_j]
0 <= u_j, v_j < n
The input is generated such that edges represents a valid tree.

Roadmap

Brute Force Baseline
Core Insight
Algorithm Walkthrough
Edge Cases
Full Annotated Code
Interactive Study Demo
Complexity Analysis

Step 01

Brute Force Baseline

Problem summary: You are given an integer n and an undirected, weighted tree rooted at node 0 with n nodes numbered from 0 to n - 1. This is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi, wi] indicates an edge from node ui to vi with weight wi. The weighted median node is defined as the first node x on the path from ui to vi such that the sum of edge weights from ui to x is greater than or equal to half of the total path weight. You are given a 2D integer array queries. For each queries[j] = [uj, vj], determine the weighted median node along the path from uj to vj. Return an array ans, where ans[j] is the node index of the weighted median for queries[j].

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Binary Search · Dynamic Programming · Bit Manipulation · Tree

Example 1

2
[[0,1,7]]
[[1,0],[0,1]]

Example 2

3
[[0,1,2],[2,0,4]]
[[0,1],[2,0],[1,2]]

Example 3

5
[[0,1,2],[0,2,5],[1,3,1],[2,4,3]]
[[3,4],[1,2]]

Step 02

Core Insight

What unlocks the optimal approach

Use binary lifting and lowest common ancestor.
Let the query nodes be <code>u</code> and <code>v</code>, with lowest common ancestor <code>l</code> and total path weight <code>tot</code>.
If the median lies on the path from <code>u</code> up to <code>l</code>: find the first node where <code>2 * sum >= tot</code> (equivalently, the last where <code>2 * sum < tot</code> and move one node above).
Otherwise, it lies on the path from <code>v</code> up to <code>l</code>: use the same <code>2 * sum >= tot</code> criterion as you climb.
In both cases, binary lifting with sparse tables lets you jump by powers of two while tracking cumulative weights to locate the weighted median in O(log n)

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
// package main
// 
// import "math/bits"
// 
// // https://space.bilibili.com/206214
// func findMedian(n int, edges [][]int, queries [][]int) []int {
// 	type edge struct{ to, wt int }
// 	g := make([][]edge, n)
// 	for _, e := range edges {
// 		x, y, wt := e[0], e[1], e[2]
// 		g[x] = append(g[x], edge{y, wt})
// 		g[y] = append(g[y], edge{x, wt})
// 	}
// 
// 	pa := make([][17]int, n)
// 	dep := make([]int, n)
// 	dis := make([]int, n)
// 
// 	var dfs func(int, int)
// 	dfs = func(x, p int) {
// 		pa[x][0] = p
// 		for _, e := range g[x] {
// 			y := e.to
// 			if y == p {
// 				continue
// 			}
// 			dep[y] = dep[x] + 1
// 			dis[y] = dis[x] + e.wt
// 			dfs(y, x)
// 		}
// 	}
// 	dfs(0, -1)
// 
// 	mx := bits.Len(uint(n))
// 	for i := range mx - 1 {
// 		for x := range pa {
// 			p := pa[x][i]
// 			if p != -1 {
// 				pa[x][i+1] = pa[p][i]
// 			} else {
// 				pa[x][i+1] = -1
// 			}
// 		}
// 	}
// 
// 	uptoDep := func(x, d int) int {
// 		for k := uint(dep[x] - d); k > 0; k &= k - 1 {
// 			x = pa[x][bits.TrailingZeros(k)]
// 		}
// 		return x
// 	}
// 
// 	// 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
// 	getLCA := func(x, y int) int {
// 		if dep[x] > dep[y] {
// 			x, y = y, x
// 		}
// 		y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
// 		if y == x {
// 			return x
// 		}
// 		for i := mx - 1; i >= 0; i-- {
// 			px, py := pa[x][i], pa[y][i]
// 			if px != py {
// 				x, y = px, py // 同时往上跳 2^i 步
// 			}
// 		}
// 		return pa[x][0]
// 	}
// 
// 	// 从 x 往上跳【至多】d 距离，返回最远能到达的节点 
// 	uptoDis := func(x, d int) int {
// 		dx := dis[x]
// 		for i := mx - 1; i >= 0; i-- {
// 			p := pa[x][i]
// 			if p != -1 && dx-dis[p] <= d { // 可以跳至多 d
// 				x = p
// 			}
// 		}
// 		return x
// 	}
// 
// 	// 以上是 LCA 模板
// 
// 	ans := make([]int, len(queries))
// 	for i, q := range queries {
// 		x, y := q[0], q[1]
// 		if x == y {
// 			ans[i] = x
// 			continue
// 		}
// 		lca := getLCA(x, y)
// 		disXY := dis[x] + dis[y] - dis[lca]*2
// 		half := (disXY + 1) / 2
// 		if dis[x]-dis[lca] >= half { // 答案在 x-lca 路径中
// 			// 先往上跳至多 half-1，然后再跳一步，就是至少 half
// 			to := uptoDis(x, half-1)
// 			ans[i] = pa[to][0] // 再跳一步
// 		} else { // 答案在 y-lca 路径中
// 			// 从 y 出发至多 disXY-half，就是从 x 出发至少 half
// 			ans[i] = uptoDis(y, disXY-half) 
// 		}
// 	}
// 	return ans
// }

// Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
package main

import "math/bits"

// https://space.bilibili.com/206214
func findMedian(n int, edges [][]int, queries [][]int) []int {
	type edge struct{ to, wt int }
	g := make([][]edge, n)
	for _, e := range edges {
		x, y, wt := e[0], e[1], e[2]
		g[x] = append(g[x], edge{y, wt})
		g[y] = append(g[y], edge{x, wt})
	}

	pa := make([][17]int, n)
	dep := make([]int, n)
	dis := make([]int, n)

	var dfs func(int, int)
	dfs = func(x, p int) {
		pa[x][0] = p
		for _, e := range g[x] {
			y := e.to
			if y == p {
				continue
			}
			dep[y] = dep[x] + 1
			dis[y] = dis[x] + e.wt
			dfs(y, x)
		}
	}
	dfs(0, -1)

	mx := bits.Len(uint(n))
	for i := range mx - 1 {
		for x := range pa {
			p := pa[x][i]
			if p != -1 {
				pa[x][i+1] = pa[p][i]
			} else {
				pa[x][i+1] = -1
			}
		}
	}

	uptoDep := func(x, d int) int {
		for k := uint(dep[x] - d); k > 0; k &= k - 1 {
			x = pa[x][bits.TrailingZeros(k)]
		}
		return x
	}

	// 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
	getLCA := func(x, y int) int {
		if dep[x] > dep[y] {
			x, y = y, x
		}
		y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
		if y == x {
			return x
		}
		for i := mx - 1; i >= 0; i-- {
			px, py := pa[x][i], pa[y][i]
			if px != py {
				x, y = px, py // 同时往上跳 2^i 步
			}
		}
		return pa[x][0]
	}

	// 从 x 往上跳【至多】d 距离，返回最远能到达的节点 
	uptoDis := func(x, d int) int {
		dx := dis[x]
		for i := mx - 1; i >= 0; i-- {
			p := pa[x][i]
			if p != -1 && dx-dis[p] <= d { // 可以跳至多 d
				x = p
			}
		}
		return x
	}

	// 以上是 LCA 模板

	ans := make([]int, len(queries))
	for i, q := range queries {
		x, y := q[0], q[1]
		if x == y {
			ans[i] = x
			continue
		}
		lca := getLCA(x, y)
		disXY := dis[x] + dis[y] - dis[lca]*2
		half := (disXY + 1) / 2
		if dis[x]-dis[lca] >= half { // 答案在 x-lca 路径中
			// 先往上跳至多 half-1，然后再跳一步，就是至少 half
			to := uptoDis(x, half-1)
			ans[i] = pa[to][0] // 再跳一步
		} else { // 答案在 y-lca 路径中
			// 从 y 出发至多 disXY-half，就是从 x 出发至少 half
			ans[i] = uptoDis(y, disXY-half) 
		}
	}
	return ans
}

# Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
from collections import deque
from typing import List

class Solution:
    def findMedian(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(n)]
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))
            
        parent = [-1] * n
        depth = [0] * n
        dist = [0] * n
        LOG = 18  # Sufficient for 10^5 nodes
        up = [[-1] * LOG for _ in range(n)]
        
        # BFS to build the tree structure (parent, depth, dist)
        queue = deque([0])
        # Standard BFS
        while queue:
            u = queue.popleft()
            for v, w in adj[u]:
                if v != parent[u]:
                    parent[v] = u
                    depth[v] = depth[u] + 1
                    dist[v] = dist[u] + w
                    queue.append(v)
        
        # Initialize binary lifting table
        for u in range(n):
            up[u][0] = parent[u]
            
        for i in range(1, LOG):
            for u in range(n):
                if up[u][i-1] != -1:
                    up[u][i] = up[up[u][i-1]][i-1]
                else:
                    up[u][i] = -1
                    
        def get_lca(u, v):
            if depth[u] < depth[v]:
                u, v = v, u
            
            diff = depth[u] - depth[v]
            for i in range(LOG):
                if (diff >> i) & 1:
                    u = up[u][i]
            
            if u == v:
                return u
            
            for i in range(LOG - 1, -1, -1):
                if up[u][i] != up[v][i]:
                    u = up[u][i]
                    v = up[v][i]
            
            return up[u][0]

        ans = []
        for u, v in queries:
            lca = get_lca(u, v)
            total_dist = dist[u] + dist[v] - 2 * dist[lca]
            dist_u_lca = dist[u] - dist[lca]
            
            # Check if the median is on the path segment u -> lca
            # We check if dist(u, lca) >= total_dist / 2
            if 2 * dist_u_lca >= total_dist:
                target_2dist = 2 * dist[u] - total_dist
                # We want the node x closest to u (deepest) such that 2*dist[x] <= target_2dist.
                # Check if u itself is the answer
                if 2 * dist[u] <= target_2dist:
                    ans.append(u)
                else:
                    # Lift u to the highest node that is INVALID (2*dist > target)
                    # The parent of that node will be the first VALID node (closest to u)
                    curr = u
                    for i in range(LOG - 1, -1, -1):
                        if up[curr][i] != -1:
                            if 2 * dist[up[curr][i]] > target_2dist:
                                curr = up[curr][i]
                    ans.append(up[curr][0])
            else:
                # Median is on path segment lca -> v
                # We want the node x closest to lca (shallowest) such that dist(u, x) >= total_dist / 2
                # Equivalent to: 2*dist[x] >= total_dist - 2*dist[u] + 4*dist[lca]
                target_2dist = total_dist - 2 * dist[u] + 4 * dist[lca]
                
                # We want the highest ancestor of v that satisfies the condition (VALID)
                # Lift v as long as the destination is VALID
                curr = v
                for i in range(LOG - 1, -1, -1):
                    if up[curr][i] != -1:
                        if 2 * dist[up[curr][i]] >= target_2dist:
                            curr = up[curr][i]
                ans.append(curr)
        
        return ans

// Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
// package main
// 
// import "math/bits"
// 
// // https://space.bilibili.com/206214
// func findMedian(n int, edges [][]int, queries [][]int) []int {
// 	type edge struct{ to, wt int }
// 	g := make([][]edge, n)
// 	for _, e := range edges {
// 		x, y, wt := e[0], e[1], e[2]
// 		g[x] = append(g[x], edge{y, wt})
// 		g[y] = append(g[y], edge{x, wt})
// 	}
// 
// 	pa := make([][17]int, n)
// 	dep := make([]int, n)
// 	dis := make([]int, n)
// 
// 	var dfs func(int, int)
// 	dfs = func(x, p int) {
// 		pa[x][0] = p
// 		for _, e := range g[x] {
// 			y := e.to
// 			if y == p {
// 				continue
// 			}
// 			dep[y] = dep[x] + 1
// 			dis[y] = dis[x] + e.wt
// 			dfs(y, x)
// 		}
// 	}
// 	dfs(0, -1)
// 
// 	mx := bits.Len(uint(n))
// 	for i := range mx - 1 {
// 		for x := range pa {
// 			p := pa[x][i]
// 			if p != -1 {
// 				pa[x][i+1] = pa[p][i]
// 			} else {
// 				pa[x][i+1] = -1
// 			}
// 		}
// 	}
// 
// 	uptoDep := func(x, d int) int {
// 		for k := uint(dep[x] - d); k > 0; k &= k - 1 {
// 			x = pa[x][bits.TrailingZeros(k)]
// 		}
// 		return x
// 	}
// 
// 	// 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
// 	getLCA := func(x, y int) int {
// 		if dep[x] > dep[y] {
// 			x, y = y, x
// 		}
// 		y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
// 		if y == x {
// 			return x
// 		}
// 		for i := mx - 1; i >= 0; i-- {
// 			px, py := pa[x][i], pa[y][i]
// 			if px != py {
// 				x, y = px, py // 同时往上跳 2^i 步
// 			}
// 		}
// 		return pa[x][0]
// 	}
// 
// 	// 从 x 往上跳【至多】d 距离，返回最远能到达的节点 
// 	uptoDis := func(x, d int) int {
// 		dx := dis[x]
// 		for i := mx - 1; i >= 0; i-- {
// 			p := pa[x][i]
// 			if p != -1 && dx-dis[p] <= d { // 可以跳至多 d
// 				x = p
// 			}
// 		}
// 		return x
// 	}
// 
// 	// 以上是 LCA 模板
// 
// 	ans := make([]int, len(queries))
// 	for i, q := range queries {
// 		x, y := q[0], q[1]
// 		if x == y {
// 			ans[i] = x
// 			continue
// 		}
// 		lca := getLCA(x, y)
// 		disXY := dis[x] + dis[y] - dis[lca]*2
// 		half := (disXY + 1) / 2
// 		if dis[x]-dis[lca] >= half { // 答案在 x-lca 路径中
// 			// 先往上跳至多 half-1，然后再跳一步，就是至少 half
// 			to := uptoDis(x, half-1)
// 			ans[i] = pa[to][0] // 再跳一步
// 		} else { // 答案在 y-lca 路径中
// 			// 从 y 出发至多 disXY-half，就是从 x 出发至少 half
// 			ans[i] = uptoDis(y, disXY-half) 
// 		}
// 	}
// 	return ans
// }

// Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3585: Find Weighted Median Node in Tree
// package main
// 
// import "math/bits"
// 
// // https://space.bilibili.com/206214
// func findMedian(n int, edges [][]int, queries [][]int) []int {
// 	type edge struct{ to, wt int }
// 	g := make([][]edge, n)
// 	for _, e := range edges {
// 		x, y, wt := e[0], e[1], e[2]
// 		g[x] = append(g[x], edge{y, wt})
// 		g[y] = append(g[y], edge{x, wt})
// 	}
// 
// 	pa := make([][17]int, n)
// 	dep := make([]int, n)
// 	dis := make([]int, n)
// 
// 	var dfs func(int, int)
// 	dfs = func(x, p int) {
// 		pa[x][0] = p
// 		for _, e := range g[x] {
// 			y := e.to
// 			if y == p {
// 				continue
// 			}
// 			dep[y] = dep[x] + 1
// 			dis[y] = dis[x] + e.wt
// 			dfs(y, x)
// 		}
// 	}
// 	dfs(0, -1)
// 
// 	mx := bits.Len(uint(n))
// 	for i := range mx - 1 {
// 		for x := range pa {
// 			p := pa[x][i]
// 			if p != -1 {
// 				pa[x][i+1] = pa[p][i]
// 			} else {
// 				pa[x][i+1] = -1
// 			}
// 		}
// 	}
// 
// 	uptoDep := func(x, d int) int {
// 		for k := uint(dep[x] - d); k > 0; k &= k - 1 {
// 			x = pa[x][bits.TrailingZeros(k)]
// 		}
// 		return x
// 	}
// 
// 	// 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
// 	getLCA := func(x, y int) int {
// 		if dep[x] > dep[y] {
// 			x, y = y, x
// 		}
// 		y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
// 		if y == x {
// 			return x
// 		}
// 		for i := mx - 1; i >= 0; i-- {
// 			px, py := pa[x][i], pa[y][i]
// 			if px != py {
// 				x, y = px, py // 同时往上跳 2^i 步
// 			}
// 		}
// 		return pa[x][0]
// 	}
// 
// 	// 从 x 往上跳【至多】d 距离，返回最远能到达的节点 
// 	uptoDis := func(x, d int) int {
// 		dx := dis[x]
// 		for i := mx - 1; i >= 0; i-- {
// 			p := pa[x][i]
// 			if p != -1 && dx-dis[p] <= d { // 可以跳至多 d
// 				x = p
// 			}
// 		}
// 		return x
// 	}
// 
// 	// 以上是 LCA 模板
// 
// 	ans := make([]int, len(queries))
// 	for i, q := range queries {
// 		x, y := q[0], q[1]
// 		if x == y {
// 			ans[i] = x
// 			continue
// 		}
// 		lca := getLCA(x, y)
// 		disXY := dis[x] + dis[y] - dis[lca]*2
// 		half := (disXY + 1) / 2
// 		if dis[x]-dis[lca] >= half { // 答案在 x-lca 路径中
// 			// 先往上跳至多 half-1，然后再跳一步，就是至少 half
// 			to := uptoDis(x, half-1)
// 			ans[i] = pa[to][0] // 再跳一步
// 		} else { // 答案在 y-lca 路径中
// 			// 从 y 出发至多 disXY-half，就是从 x 出发至少 half
// 			ans[i] = uptoDis(y, disXY-half) 
// 		}
// 	}
// 	return ans
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(log n)

Space

O(1)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.

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.