← Google Interview Insights

Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Got a tree problem at Google for a SWE role. One question, classic graph stuff but the distance sum angle made it less obvious than it looked.

Questions Asked (1)

Q1

Given a tree with N nodes (0 to N-1) and N-1 undirected edges, compute the sum of distances from each node to every other node. Return an array where the ith element is the total distance from node i.

Algorithms & Data Structures
Author's notes

My first instinct was brute force BFS from every node, which is O(N^2) and works for small inputs but N can be 3*10^4 so that's not going to cut it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pass tree DP (rerooting technique): first compute subtree sizes and the sum of distances from the root via a post-order DFS, then propagate the answer to all nodes via a pre-order DFS using the relation ans[child] = ans[parent] + N - 2 * subtree_size[child]. This achieves O(N) time and O(N) space, which is optimal.

Pro tip: Mention that the rerooting recurrence is derived by observing that moving the root from parent to child decreases distances to the child's subtree by 1 and increases distances to all other nodes by 1, yielding the formula. This shows deep understanding and avoids brute-force O(N^2).

1. Clarify and Define

Confirm the tree is connected, undirected, and has N-1 edges. Define the output array ans[i] as the sum of distances from node i to all other nodes.

2. First DFS: Subtree Sizes and Root Sum

Root the tree at node 0. Perform a post-order DFS to compute subtree sizes (sub[i]) and the sum of distances from the root to all nodes (ans[0]).

3. Second DFS: Reroot to Compute All Answers

Perform a pre-order DFS. For each child v of u, compute ans[v] = ans[u] + N - 2 * sub[v]. This propagates the answer to all nodes.

4. Return the Result

After the second DFS, ans array contains the required sums for all nodes. Return it.

Key Points to Mention

  • Tree DP / Rerooting technique
  • Time complexity O(N) and space complexity O(N)
  • Subtree size computation via post-order DFS
  • Rerooting recurrence: ans[child] = ans[parent] + N - 2 * subtree_size[child]
  • Handling large N (up to 10^5 or more) efficiently
  • Avoiding brute-force O(N^2) approach

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.