Design mutable sum-tree with fast queries

Q: Design mutable sum-tree with fast queries

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Airbnb.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Airbnb during technical interviews.

Question

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

PracHub · Accepted Answer

from collections import deque

def solution(edges, leaf_values, operations):
    nodes = {}

def ensure(nid):
        if nid not in nodes:
            nodes[nid] = {'parent': None, 'children': [], 'sum': 0, 'is_leaf': False}

for parent, child in edges:
        ensure(parent)
        ensure(child)
        nodes[parent]['children'].append(child)
        nodes[child]['parent'] = parent

for nid, value in leaf_values.items():
        ensure(nid)
        nodes[nid]['sum'] = value

for nid, info in nodes.items():
        if info['children']:
            info['is_leaf'] = False
            info['sum'] = 0
        else:
            info['is_leaf'] = True

pending = {nid: len(info['children']) for nid, info in nodes.items()}
    queue = deque([nid for nid, count in pending.items() if count == 0])

while queue:
        nid = queue.popleft()
        parent = nodes[nid]['parent']
        if parent is not None:
            nodes[parent]['sum'] += nodes[nid]['sum']
            pending[parent] -= 1
            if pending[parent] == 0:
                queue.append(parent)

def propagate(parent, delta):
        while parent is not None:
            nodes[parent]['sum'] += delta
            parent = nodes[parent]['parent']

def delete_descendants(children):
        stack = list(children)
        while stack:
            nid = stack.pop()
            stack.extend(nodes[nid]['children'])
            del nodes[nid]

answer = []

for op in operations:
        kind = op[0]

if kind == 'get':
            answer.append(nodes[op[1]]['sum'])

elif kind == 'toLeaf':
            node_id, value = op[1], op[2]
            info = nodes[node_id]
            old_sum = info['sum']

if not info['is_leaf']:
                delete_descendants(info['children'])
                info['children'] = []

info['is_leaf'] = True
            info['sum'] = value
            propagate(info['parent'], value - old_sum)

else:  # toParent
            node_id, new_edges, new_leaf_values = op[1], op[2], op[3]
            root = nodes[node_id]
            old_sum = root['sum']

subtree_ids = {node_id}
            for parent, child in new_edges:
                subtree_ids.add(parent)
                subtree_ids.add(child)
            subtree_ids.update(new_leaf_values.keys())

for nid in subtree_ids:
                if nid != node_id and nid not in nodes:
                    nodes[nid] = {'parent': None, 'children': [], 'sum': 0, 'is_leaf': False}

children_map = {nid: [] for nid in subtree_ids}
            local_parent = {}
            for parent, child in new_edges:
                children_map[parent].append(child)
                local_parent[child] = parent

root['is_leaf'] = False
            root['children'] = children_map.get(node_id, [])
            root['sum'] = 0

for nid in subtree_ids:
                if nid == node_id:
                    continue
                nodes[nid]['parent'] = local_parent.get(nid)
                nodes[nid]['children'] = children_map.get(nid, [])
                nodes[nid]['is_leaf'] = nid in new_leaf_values
                nodes[nid]['sum'] = new_leaf_values[nid] if nid in new_leaf_values else 0

stack = [(node_id, False)]
            while stack:
                nid, visited = stack.pop()
                if not visited:
                    stack.append((nid, True))
                    for child in nodes[nid]['children']:
                        stack.append((child, False))
                else:
                    if nodes[nid]['is_leaf']:
                        nodes[nid]['sum'] = new_leaf_values.get(nid, nodes[nid]['sum'])
                    else:
                        total = 0
                        for child in nodes[nid]['children']:

Quick Overview

Examples

Solution

Hints

Quick Overview