Total Distance From Every Node
HardTrees
Problem
Treat a binary tree as a network where each edge has length 1. For every node, compute the sum of its distances to all other nodes.
Return these sums in level order (the order in which a left-to-right, top-down traversal visits the nodes).
Example 1
- Input:
- root = [1, 2, 3]
- Output:
- [2, 3, 3]
The root is 1 away from both leaves; each leaf is 1 from the root and 2 from the other leaf.
Example 2
- Input:
- root = [1, 2, 3, 4, 5, 6, 7]
- Output:
- [10, 11, 11, 16, 16, 16, 16]
Constraints
- 0 ≤ number of nodes ≤ 3 · 10^4
- -1000 ≤ node.val ≤ 1000 (values may repeat; they play no role)
Hint
Show the first hint
Computing a BFS from every node costs O(n²). Can the answer for a child be derived from its parent's answer?
Walkthrough
How to approach it
01Clarify before coding
- Distances count edges, in both directions through parents? Yes, the tree is undirected for this purpose.
- Output order? Level order of the nodes, not by value (values may repeat).
- Empty tree? Return [].
02Brute force
Run a BFS from every node over the undirected tree and sum the distances.
Cost: O(n²): 9 · 10^8 steps for 3 · 10^4 nodes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.