Find Subtree Sizes After Changes — Problem & Solution
Find Subtree Sizes After Changes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find Subtree Sizes After Changes is a medium coding problem on arrays, strings and hash table, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Depth-First Search, Trees
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A tree has n nodes numbered 0 to n - 1 and is rooted at node 0. It is given by parent, where parent[i] is the parent of node i and parent[0] = -1. Node i carries the letter s[i].
All at once, for every node x from 1 to n - 1: find the closest ancestor y of x (in the original tree) with s[y] == s[x]. If such a y exists, cut the edge between x and its parent and make y the new parent of x. If none exists, x keeps its parent.
Return an array answer of length n where answer[i] is the number of nodes in the subtree of node i in the final tree.
Example 1
Input: parent = [-1,0,0,1,1,1], s = "abaabc"
Output: [6,3,1,1,1,1]
Explanation: Node 3 ('a') has the ancestor 0 ('a'), so it moves under node 0. Every other node keeps its parent.
Example 2
Input: parent = [-1,0,4,0,1], s = "abbba"
Output: [5,2,1,1,1]
Explanation: Node 4 ('a') moves under node 0 and node 2 ('b') moves under node 1; node 1 then holds nodes 1 and 2.
Example 3
Input: parent = [-1], s = "z"
Output: [1]
Constraints
n == parent.length == s.length1 <= n <= 10^50 <= parent[i] <= n - 1 for all i >= 1parent[0] == -1parent represents a valid trees consists only of lowercase English letters
Hints for Find Subtree Sizes After Changes
Hint 1
The changes are simultaneous and use the original tree, so every node's new parent can be decided independently.
Hint 2
Walk the tree depth-first. If you keep, for every letter, the deepest node with that letter on the current root-to-node path, the closest matching ancestor is just a lookup.
Hint 3
Remember the old entry when you overwrite a letter's slot on entering a node, and restore it when you leave. Then a new parent is always an old ancestor, so a reverse pre-order pass adds up the new subtree sizes.
How to solve Find Subtree Sizes After Changes
A depth-first walk keeps the current root-to-node path; a 26-slot table holding the deepest node of each letter on that path answers "closest ancestor with the same letter" in O(1). Since the new parent is an ancestor, the pre-order of the original tree still lists every new parent before its children.
Approach
- Build the children lists from
parent. - DFS from 0 with an explicit stack. On entering
x(not the root): iflast[s[x]]is set, the new parent ofxis that node. Save the oldlast[s[x]], set it tox, and recordxin pre-order. - On leaving
x, restorelast[s[x]]to the saved value. - Set every size to 1 and walk the pre-order backwards, adding
size[x]tosize[newParent[x]].
Why it works
When x is entered, the table holds exactly the nodes on the path from the root to x's parent, the deepest one per letter, because every node leaving the path restores what it overwrote. So the lookup is the closest matching ancestor in the original tree, as the simultaneous rule requires. The new parent precedes x in pre-order, so the backward accumulation sees every child before its parent.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Do not apply the moves one at a time and look up ancestors in the changing tree — the rule is defined on the original tree.
- Forgetting to restore the letter slot on exit lets a node in one branch adopt a node from a sibling branch.
- The root never changes its parent.
Reference solution
Python
from typing import List
def findSubtreeSizes(parent: List[int], s: str) -> List[int]:
n = len(parent)
children = [[] for _ in range(n)]
for i in range(1, n):
children[parent[i]].append(i)
last = [-1] * 26
saved = [-1] * n
newp = parent[:]
pre = []
stack = [0]
while stack:
x = stack.pop()
if x >= 0:
c = ord(s[x]) - 97
if x != 0 and last[c] != -1:
newp[x] = last[c]
saved[x] = last[c]
last[c] = x
pre.append(x)
stack.append(~x)
stack.extend(children[x])
else:
x = ~x
last[ord(s[x]) - 97] = saved[x]
size = [1] * n
for x in reversed(pre):
if x != 0:
size[newp[x]] += size[x]
return sizeJava
public static int[] findSubtreeSizes(int[] parent, String s) {
int n = parent.length;
List<List<Integer>> children = new ArrayList<>();
for (int i = 0; i < n; i++) children.add(new ArrayList<>());
for (int i = 1; i < n; i++) children.get(parent[i]).add(i);
int[] last = new int[26];
Arrays.fill(last, -1);
int[] saved = new int[n], newp = parent.clone(), size = new int[n], pre = new int[n];
Arrays.fill(size, 1);
int[] stack = new int[2 * n + 1];
int top = 0, cnt = 0;
stack[top++] = 0;
while (top > 0) {
int x = stack[--top];
if (x >= 0) {
int c = s.charAt(x) - 'a';
if (x != 0 && last[c] != -1) newp[x] = last[c];
saved[x] = last[c];
last[c] = x;
pre[cnt++] = x;
stack[top++] = -x - 1;
for (int y : children.get(x)) stack[top++] = y;
} else {
int y = -x - 1;
last[s.charAt(y) - 'a'] = saved[y];
}
}
for (int t = n - 1; t > 0; t--) size[newp[pre[t]]] += size[pre[t]];
return size;
}C++
vector<int> findSubtreeSizes(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>> children(n);
for (int i = 1; i < n; i++) children[parent[i]].push_back(i);
vector<int> last(26, -1), saved(n, -1), newp(parent), size(n, 1), pre, stack = {0};
while (!stack.empty()) {
int x = stack.back();
stack.pop_back();
if (x >= 0) {
int c = s[x] - 'a';
if (x != 0 && last[c] != -1) newp[x] = last[c];
saved[x] = last[c];
last[c] = x;
pre.push_back(x);
stack.push_back(-x - 1);
for (int y : children[x]) stack.push_back(y);
} else {
int y = -x - 1;
last[s[y] - 'a'] = saved[y];
}
}
for (int t = n - 1; t > 0; t--) size[newp[pre[t]]] += size[pre[t]];
return size;
}JavaScript
var findSubtreeSizes = function(parent, s) {
var n = parent.length;
var children = [], saved = [], newp = [], size = [];
for (var i = 0; i < n; i++) { children.push([]); saved.push(-1); newp.push(parent[i]); size.push(1); }
for (var j = 1; j < n; j++) children[parent[j]].push(j);
var last = [];
for (var c = 0; c < 26; c++) last.push(-1);
var pre = [], stack = [0];
while (stack.length > 0) {
var x = stack.pop();
if (x >= 0) {
var ch = s.charCodeAt(x) - 97;
if (x !== 0 && last[ch] !== -1) newp[x] = last[ch];
saved[x] = last[ch];
last[ch] = x;
pre.push(x);
stack.push(-x - 1);
for (var k = 0; k < children[x].length; k++) stack.push(children[x][k]);
} else {
var y = -x - 1;
last[s.charCodeAt(y) - 97] = saved[y];
}
}
for (var t = n - 1; t > 0; t--) size[newp[pre[t]]] += size[pre[t]];
return size;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.