Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Sum of Distances in Tree
Bookmark
Input
Standard
Small
Path
Custom
n
=
6
,
edges
=
[[0,1],[0,2],[2,3],[2,4],[2,5]]
0
root
1
2
3
4
5
setup
answer[0] = 0
count
0
1
1
1
2
1
3
1
4
1
5
1
answer
0
0
1
0
2
0
3
0
4
0
5
0
root at
0
· count[] = subtree sizes · answer[] = distance sums
0
root
1
2
3
4
5
setup
answer[0] = 0
count
0
1
1
1
2
1
3
1
4
1
5
1
answer
0
0
1
0
2
0
3
0
4
0
5
0
root at
0
· count[] = subtree sizes · answer[] = distance sums
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 0
count
0
1
1
1
2
2
3
1
4
1
5
1
answer
0
0
1
0
2
0
3
0
4
0
5
0
count[
2
] += count[
5
] =
2
(subtree size bubbles up)
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 1
count
0
1
1
1
2
3
3
1
4
1
5
1
answer
0
1
1
0
2
0
3
0
4
0
5
0
count[
2
] += count[
4
] =
3
(subtree size bubbles up)
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 3
count
0
1
1
1
2
4
3
1
4
1
5
1
answer
0
3
1
0
2
0
3
0
4
0
5
0
answer[0] += count[
3
] =
3
(each is 1 step farther from the root)
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 7
count
0
5
1
1
2
4
3
1
4
1
5
1
answer
0
7
1
0
2
0
3
0
4
0
5
0
answer[0] += count[
2
] =
7
(each is 1 step farther from the root)
0
root
1
2
3
4
5
Pass 1 · post-order
answer[0] = 8
count
0
6
1
1
2
4
3
1
4
1
5
1
answer
0
8
1
0
2
0
3
0
4
0
5
0
answer[0] += count[
1
] =
8
(each is 1 step farther from the root)
0
root
1
2
3
4
5
Pass 2 · pre-order
answer[0] = 8
count
0
6
1
1
2
4
3
1
4
1
5
1
answer
0
8
1
0
2
0
3
0
4
0
5
0
pass 2: reroot into node
1
0
root
1
2
3
4
5
Pass 2 · pre-order
answer[0] = 8
count
0
6
1
1
2
4
3
1
4
1
5
1
answer
0
8
1
12
2
6
3
0
4
0
5
0
pass 2: reroot into node
3
0
root
1
2
3
4
5
Pass 2 · pre-order
answer[0] = 8
count
0
6
1
1
2
4
3
1
4
1
5
1
answer
0
8
1
12
2
6
3
10
4
10
5
0
answer[
4
] = answer[
2
] +
6
− 2·count[
4
] =
10
0
root
1
2
3
4
5
done
answer[0] = 8
count
0
6
1
1
2
4
3
1
4
1
5
1
answer
0
8
1
12
2
6
3
10
4
10
5
10
answer = [8, 12, 6, 10, 10, 10]
algo
master
.
io
Step:
Sum of Distances in Tree: distance sum for every node
0 / 29
Input
Standard
Small
Path
Custom
n
=
6
,
edges
=
[[0,1],[0,2],[2,3],[2,4],[2,5]]
0 / 29
algo
master
.
io
Step:
Sum of Distances in Tree: distance sum for every node
