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].
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 |
2 |
Constraints:
2 <= n <= 105edges.length == n - 1edges[i] == [ui, vi, wi]0 <= ui, vi < n1 <= wi <= 1091 <= queries.length <= 105queries[j] == [uj, vj]0 <= uj, vj < nedges represents a valid tree.Problem Overview: You are given a tree where each node has an associated weight. The goal is to find a weighted median node: a node such that if you remove it, every resulting connected component has total weight ≤ half of the total weight of the entire tree.
Approach 1: Brute Force Component Check (O(n^2) time, O(n) space)
Try every node as the candidate median. For each node, temporarily treat it as removed and run a DFS into each adjacent subtree to compute the total weight of that component. Track the largest component weight. If the maximum component weight is ≤ totalWeight / 2, that node satisfies the weighted median condition. This approach is simple and directly models the definition, but each candidate requires traversing large portions of the tree again. With n nodes, this leads to O(n^2) time in the worst case.
Approach 2: Subtree Weight DFS (Optimal) (O(n) time, O(n) space)
Compute subtree weights using a single depth-first search. Let subtree[u] represent the total weight of node u and all nodes below it. After computing these values, evaluate each node as a candidate median. For node u, the weight of every child component is simply subtree[child]. The remaining component (the "parent side") has weight totalWeight - subtree[u]. The largest of these component weights determines whether u is valid. If all components are ≤ totalWeight / 2, you found the weighted median node.
This works because subtree sums allow constant-time evaluation of each component after a single traversal. The tree is processed once to compute weights and once more to check the condition, giving linear time overall. The approach relies heavily on tree structure properties and precomputed subtree aggregates, a common pattern in dynamic programming on trees.
Recommended for interviews: The subtree-weight DFS approach. Interviewers expect you to recognize that recomputing component weights repeatedly is wasteful. Precomputing subtree sums reduces the complexity from O(n^2) to O(n). Starting with the brute-force idea shows you understand the definition, but optimizing it with DFS aggregation demonstrates strong tree algorithm skills.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Component DFS | O(n^2) | O(n) | Useful for understanding the definition of weighted median or when constraints are very small |
| Subtree Weight DFS (Optimal) | O(n) | O(n) | General solution for large trees; precompute subtree sums and check each node efficiently |
| Tree DP / Rerooting Variant | O(n) | O(n) | Useful when the problem extends to multiple queries or requires evaluating properties from different roots |
3585. Find Weighted Median Node in Tree | LeetCode weekly contest 454 • Amit Dhyani • 1,187 views views
Watch 4 more video solutions →Practice Find Weighted Median Node in Tree with our built-in code editor and test cases.
Practice on FleetCode