Find Subtree Sizes After Changes - Video Solutions

Problem Overview: You are given a rooted tree defined by a parent array and a string s where s[i] is the label of node i. Each node may reconnect to the nearest ancestor that has the same character. After applying these changes simultaneously, compute the size of every node’s subtree in the new tree.

Approach 1: DFS with Ancestor Character Tracking (O(n) time, O(n) space)

Build the original tree using an adjacency list from the parent array, then run a Depth-First Search. During DFS, maintain a map from character to the most recent ancestor index with that character. When visiting node u, check whether its character already appears in the map. If it does, the new parent becomes that ancestor; otherwise the original parent remains. Maintain a temporary stack/list for each character so that when DFS backtracks the previous ancestor is restored. Once the new parent for each node is determined, construct the updated tree and run another DFS to compute subtree sizes. This works because every node is visited once and character lookups are constant-time via a hash table.

Approach 2: Union-Find Based Construction (O(n α(n)) time, O(n) space)

You can also treat the reattachment step as merging nodes with their closest matching ancestor using a Union-Find (Disjoint Set Union) structure. While traversing the tree with DFS, maintain the latest ancestor for each character. If node u finds a matching ancestor a, union u with a. The disjoint-set structure efficiently tracks component representatives with near-constant amortized cost α(n). After all unions are applied, rebuild the effective parent relationships and compute subtree sizes with a DFS on the resulting structure. This approach highlights connectivity management and works well when tree relationships are dynamically merged.

The core insight across both methods: every node only needs the closest ancestor with the same character. A DFS traversal naturally exposes the current ancestor chain, making it easy to track the latest node for each character. That eliminates expensive upward scans and keeps the solution linear.

Recommended for interviews: The DFS ancestor-tracking approach is the expected solution. It uses standard tree traversal, constant-time hash lookups, and processes each node exactly once for O(n) time. Discussing it shows strong understanding of DFS state management along the recursion path. The Union-Find version is a useful alternative when you want to reason about connectivity or demonstrate familiarity with disjoint-set structures.