Quick 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.

Design mutable sum-tree with fast queries

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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).

Quick Answer: 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 are given a rooted mutable tree. Each leaf stores an integer value. Every internal node's value is always the sum of its immediate children's current values, so each node also equals the sum of all leaf values in its current subtree. Implement a function that preprocesses the initial tree and then processes mutations and queries efficiently. Operations are: ('get', nodeId) to return the current value of a node, ('toLeaf', nodeId, value) to delete nodeId's current descendants and make nodeId a leaf with the given value, and ('toParent', nodeId, new_edges, new_leaf_values) to convert a current leaf into an internal node by attaching a new subtree rooted at nodeId. Return the answers to all 'get' operations in order. Your solution should correctly maintain parent/child links, subtree sums, handle negative values, allow an empty attached subtree (value 0), and avoid recursion-only approaches because the tree may be very deep.

Constraints

  • The initial structure is a valid rooted tree.
  • 1 <= total number of nodes that ever appear across the whole input <= 2 * 10^5.
  • -10^9 <= each leaf value <= 10^9, and sums may exceed 32-bit range.
  • Operations are valid: `get` and `toLeaf` reference existing nodes, `toParent` is called on a current leaf, and added node ids are not currently present in the tree.
  • If `toParent(nodeId, [], {})` is used, `nodeId` becomes an internal node with no children and value 0.

Examples

Input: ([(1, 2), (1, 3), (3, 4), (3, 5)], {2: 5, 4: 2, 5: 1}, [('get', 1), ('get', 3), ('toLeaf', 3, 10), ('get', 1), ('get', 3), ('toParent', 2, [(2, 6), (2, 7)], {6: 4, 7: -1}), ('get', 2), ('get', 1)])

Expected Output: [8, 3, 15, 10, 3, 13]

Explanation: Initially node 3 = 2 + 1 = 3 and node 1 = 5 + 3 = 8. After making node 3 a leaf with value 10, node 1 becomes 15. Then node 2 changes from leaf 5 to an internal node with children 6 and 7, so node 2 = 4 + (-1) = 3 and node 1 becomes 13.

Input: ([], {1: 7}, [('get', 1), ('toParent', 1, [], {}), ('get', 1), ('toLeaf', 1, -3), ('get', 1)])

Expected Output: [7, 0, -3]

Explanation: Single-node tree edge case. The empty `toParent` makes node 1 an internal node with no children, so its sum is 0. Converting it back to a leaf with value -3 updates the node correctly.

Hints

  1. Store each node's current subtree sum so a `get` query can be answered in O(1).
  2. After a mutation, only the changed node, any added/removed subtree nodes, and the node's ancestors are affected. Propagate a delta upward through parent pointers instead of recomputing the whole tree.

Loading coding console...