Find Weighted Median Node in Tree

Find Weighted Median Node in Tree

1. What is this problem about?

The Find Weighted Median Node in Tree interview question is a high-level graph optimization task. You are given a tree where each node has an associated weight (importance or mass). You need to find a node such that if you remove it, the total weight of any resulting connected component (subtree) is at most half of the total weight of the entire tree. This node is also known as the Weighted Centroid of the tree.

2. Why is this asked in interviews?

Google asks the Find Weighted Median Node in Tree coding problem to evaluate a candidate's mastery of Depth-First Search (DFS) and tree properties. It tests your ability to aggregate information (weight sums) from the bottom up and make global decisions based on local metrics. It is a vital skill for distributed systems design, where you might need to find a central "hub" to minimize communication costs.

3. Algorithmic pattern used

This problem follows the Post-order DFS and Centroid Finding pattern.

1. Total Weight: First, calculate the sum of all weights in the tree ($W_{total}$).
2. Subtree Weights: Perform a DFS to calculate the total weight of every subtree.
3. Centroid Check: A node $U$ is a weighted median if:
   • For every child $V$, $Weight(Subtree_V) \leq W_{total} / 2$.
   • The "upward" component $(W_{total} - Weight(Subtree_U)) \leq W_{total} / 2$.
4. Greedy Search: You can find this node by starting at the root and repeatedly moving to the child whose subtree weight exceeds $W_{total} / 2$. If no such child exists, the current node is the median.

4. Example explanation

Tree: Node 0 (weight 10) connected to Node 1 (weight 50) and Node 2 (weight 5). Total weight = 65.

• Start at 0.
• Subtree 1 weight = 50. $50 > 65/2$ (32.5).
• Move to 1.
• Node 1 has no children. The "upward" weight from 1 is $65 - 50 = 15$.
• $15 \leq 32.5$. Result: Node 1 is the weighted median.

5. Common mistakes candidates make

• Treating all nodes as weight 1: Failing to account for the specific weights provided for each node.
• Recalculating sums: Running a full DFS from every node ($O(N^2)$) instead of using one pass to store subtree sums ($O(N)$).
• Ignoring the "Upward" component: Forgetting that when you pick a node, the part of the tree "above" it (towards the original root) also forms a connected component.

6. Interview preparation tip

Master the concept of a Tree Centroid. A tree can have at most two centroids. If weights are involved, the logic remains the same: you are looking for the "balance point" of the tree's mass.