Design mutable sum-tree with fast queries
Overview
This question evaluates proficiency in designing dynamic data structures for mutable rooted trees, including maintenance of subtree sums, parent/child link management, and analysis of update and query complexities within the Coding & Algorithms domain; it emphasizes practical application of algorithmic design coupled with conceptual understanding of invariants and amortized complexity. It is commonly asked in technical interviews because it probes reasoning about correctness and performance under mutations, handling edge cases such as subtree deletion and reattachment, and the ability to specify algorithmic approaches and complexity guarantees rather than implementation details.
You're given a rooted, mutable tree. Each leaf node stores an integer value. Each internal node's value equals the sum of its immediate children's values. Design data structures and functions to: (a) return the current value of any node by id efficiently after preprocessing; and (b) support two mutations: toLeaf(nodeId, value) converts any node into a leaf with the given value (removing its prior subtree), and toParent(nodeId, subtree) converts a leaf into an internal node by attaching a provided subtree whose leaves hold integers. After any sequence of mutations, getValue(nodeId) must remain correct and efficient. Specify algorithms, update/query complexities, how you maintain parent/child links and subtree sums, and how you handle edge cases (deleting/reattaching subtrees, empty children, overflow, very deep trees).