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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Design mutable sum-tree with fast queries

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.

Input: ([(10, 11), (10, 12), (12, 13), (12, 14), (14, 15)], {11: -2, 13: 5, 15: 7}, [('get', 10), ('toLeaf', 12, 1), ('get', 10), ('get', 12), ('toParent', 11, [(11, 16), (11, 17), (16, 18)], {17: 2, 18: 3}), ('get', 11), ('get', 10)])

Expected Output: [10, -1, 1, 5, 6]

Explanation: Initially node 12 = 5 + 7 = 12 and node 10 = -2 + 12 = 10. After `toLeaf(12, 1)`, node 10 becomes -1. Then node 11 becomes an internal node with subtree sum 5, so node 10 becomes 6.

Input: ([(1, 2), (1, 3)], {2: 4, 3: 4}, [('get', 1), ('toLeaf', 1, 0), ('get', 1), ('toParent', 1, [(1, 4), (4, 5)], {5: 9}), ('get', 4), ('get', 1)])

Expected Output: [8, 0, 9, 9]

Explanation: The root starts as 8. Converting the root to a leaf makes it 0 and removes its old subtree. Attaching a new subtree gives node 4 = 9 and root node 1 = 9.

Solution

from collections import deque\n\ndef solution(edges, leaf_values, operations):\n    nodes = {}\n\n    def ensure(nid):\n        if nid not in nodes:\n            nodes[nid] = {'parent': None, 'children': [], 'sum': 0, 'is_leaf': False}\n\n    for parent, child in edges:\n        ensure(parent)\n        ensure(child)\n        nodes[parent]['children'].append(child)\n        nodes[child]['parent'] = parent\n\n    for nid, value in leaf_values.items():\n        ensure(nid)\n        nodes[nid]['sum'] = value\n\n    for nid, info in nodes.items():\n        if info['children']:\n            info['is_leaf'] = False\n            info['sum'] = 0\n        else:\n            info['is_leaf'] = True\n\n    pending = {nid: len(info['children']) for nid, info in nodes.items()}\n    queue = deque([nid for nid, count in pending.items() if count == 0])\n\n    while queue:\n        nid = queue.popleft()\n        parent = nodes[nid]['parent']\n        if parent is not None:\n            nodes[parent]['sum'] += nodes[nid]['sum']\n            pending[parent] -= 1\n            if pending[parent] == 0:\n                queue.append(parent)\n\n    def propagate(parent, delta):\n        while parent is not None:\n            nodes[parent]['sum'] += delta\n            parent = nodes[parent]['parent']\n\n    def delete_descendants(children):\n        stack = list(children)\n        while stack:\n            nid = stack.pop()\n            stack.extend(nodes[nid]['children'])\n            del nodes[nid]\n\n    answer = []\n\n    for op in operations:\n        kind = op[0]\n\n        if kind == 'get':\n            answer.append(nodes[op[1]]['sum'])\n\n        elif kind == 'toLeaf':\n            node_id, value = op[1], op[2]\n            info = nodes[node_id]\n            old_sum = info['sum']\n\n            if not info['is_leaf']:\n                delete_descendants(info['children'])\n                info['children'] = []\n\n            info['is_leaf'] = True\n            info['sum'] = value\n            propagate(info['parent'], value - old_sum)\n\n        else:  # toParent\n            node_id, new_edges, new_leaf_values = op[1], op[2], op[3]\n            root = nodes[node_id]\n            old_sum = root['sum']\n\n            subtree_ids = {node_id}\n            for parent, child in new_edges:\n                subtree_ids.add(parent)\n                subtree_ids.add(child)\n            subtree_ids.update(new_leaf_values.keys())\n\n            for nid in subtree_ids:\n                if nid != node_id and nid not in nodes:\n                    nodes[nid] = {'parent': None, 'children': [], 'sum': 0, 'is_leaf': False}\n\n            children_map = {nid: [] for nid in subtree_ids}\n            local_parent = {}\n            for parent, child in new_edges:\n                children_map[parent].append(child)\n                local_parent[child] = parent\n\n            root['is_leaf'] = False\n            root['children'] = children_map.get(node_id, [])\n            root['sum'] = 0\n\n            for nid in subtree_ids:\n                if nid == node_id:\n                    continue\n                nodes[nid]['parent'] = local_parent.get(nid)\n                nodes[nid]['children'] = children_map.get(nid, [])\n                nodes[nid]['is_leaf'] = nid in new_leaf_values\n                nodes[nid]['sum'] = new_leaf_values[nid] if nid in new_leaf_values else 0\n\n            stack = [(node_id, False)]\n            while stack:\n                nid, visited = stack.pop()\n                if not visited:\n                    stack.append((nid, True))\n                    for child in nodes[nid]['children']:\n                        stack.append((child, False))\n                else:\n                    if nodes[nid]['is_leaf']:\n                        nodes[nid]['sum'] = new_leaf_values.get(nid, nodes[nid]['sum'])\n                    else:\n                        total = 0\n                        for child in nodes[nid]['children']:\n                            total += nodes[child]['sum']\n                        nodes[nid]['sum'] = total\n\n            propagate(root['parent'], nodes[node_id]['sum'] - old_sum)\n\n    return answer

Time complexity: Preprocessing: O(n). Each `get`: O(1). Each `toLeaf`: O(k + h), where k is the number of deleted descendants and h is the height to the root. Each `toParent`: O(s + h), where s is the size of the attached subtree.. Space complexity: O(m), where m is the number of nodes currently stored in the tree..

Hints

Store each node's current subtree sum so a `get` query can be answered in O(1).
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.

Last updated: Apr 25, 2026

Loading coding console...

Quick Overview

Design mutable sum-tree with fast queries

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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

Expected Output: [8, 3, 15, 10, 3, 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.

Expected Output: [10, -1, 1, 5, 6]

Explanation: Initially node 12 = 5 + 7 = 12 and node 10 = -2 + 12 = 10. After `toLeaf(12, 1)`, node 10 becomes -1. Then node 11 becomes an internal node with subtree sum 5, so node 10 becomes 6.

Input: ([(1, 2), (1, 3)], {2: 4, 3: 4}, [('get', 1), ('toLeaf', 1, 0), ('get', 1), ('toParent', 1, [(1, 4), (4, 5)], {5: 9}), ('get', 4), ('get', 1)])

Expected Output: [8, 0, 9, 9]

Explanation: The root starts as 8. Converting the root to a leaf makes it 0 and removes its old subtree. Attaching a new subtree gives node 4 = 9 and root node 1 = 9.

Solution

from collections import deque\n\ndef solution(edges, leaf_values, operations):\n    nodes = {}\n\n    def ensure(nid):\n        if nid not in nodes:\n            nodes[nid] = {'parent': None, 'children': [], 'sum': 0, 'is_leaf': False}\n\n    for parent, child in edges:\n        ensure(parent)\n        ensure(child)\n        nodes[parent]['children'].append(child)\n        nodes[child]['parent'] = parent\n\n    for nid, value in leaf_values.items():\n        ensure(nid)\n        nodes[nid]['sum'] = value\n\n    for nid, info in nodes.items():\n        if info['children']:\n            info['is_leaf'] = False\n            info['sum'] = 0\n        else:\n            info['is_leaf'] = True\n\n    pending = {nid: len(info['children']) for nid, info in nodes.items()}\n    queue = deque([nid for nid, count in pending.items() if count == 0])\n\n    while queue:\n        nid = queue.popleft()\n        parent = nodes[nid]['parent']\n        if parent is not None:\n            nodes[parent]['sum'] += nodes[nid]['sum']\n            pending[parent] -= 1\n            if pending[parent] == 0:\n                queue.append(parent)\n\n    def propagate(parent, delta):\n        while parent is not None:\n            nodes[parent]['sum'] += delta\n            parent = nodes[parent]['parent']\n\n    def delete_descendants(children):\n        stack = list(children)\n        while stack:\n            nid = stack.pop()\n            stack.extend(nodes[nid]['children'])\n            del nodes[nid]\n\n    answer = []\n\n    for op in operations:\n        kind = op[0]\n\n        if kind == 'get':\n            answer.append(nodes[op[1]]['sum'])\n\n        elif kind == 'toLeaf':\n            node_id, value = op[1], op[2]\n            info = nodes[node_id]\n            old_sum = info['sum']\n\n            if not info['is_leaf']:\n                delete_descendants(info['children'])\n                info['children'] = []\n\n            info['is_leaf'] = True\n            info['sum'] = value\n            propagate(info['parent'], value - old_sum)\n\n        else:  # toParent\n            node_id, new_edges, new_leaf_values = op[1], op[2], op[3]\n            root = nodes[node_id]\n            old_sum = root['sum']\n\n            subtree_ids = {node_id}\n            for parent, child in new_edges:\n                subtree_ids.add(parent)\n                subtree_ids.add(child)\n            subtree_ids.update(new_leaf_values.keys())\n\n            for nid in subtree_ids:\n                if nid != node_id and nid not in nodes:\n                    nodes[nid] = {'parent': None, 'children': [], 'sum': 0, 'is_leaf': False}\n\n            children_map = {nid: [] for nid in subtree_ids}\n            local_parent = {}\n            for parent, child in new_edges:\n                children_map[parent].append(child)\n                local_parent[child] = parent\n\n            root['is_leaf'] = False\n            root['children'] = children_map.get(node_id, [])\n            root['sum'] = 0\n\n            for nid in subtree_ids:\n                if nid == node_id:\n                    continue\n                nodes[nid]['parent'] = local_parent.get(nid)\n                nodes[nid]['children'] = children_map.get(nid, [])\n                nodes[nid]['is_leaf'] = nid in new_leaf_values\n                nodes[nid]['sum'] = new_leaf_values[nid] if nid in new_leaf_values else 0\n\n            stack = [(node_id, False)]\n            while stack:\n                nid, visited = stack.pop()\n                if not visited:\n                    stack.append((nid, True))\n                    for child in nodes[nid]['children']:\n                        stack.append((child, False))\n                else:\n                    if nodes[nid]['is_leaf']:\n                        nodes[nid]['sum'] = new_leaf_values.get(nid, nodes[nid]['sum'])\n                    else:\n                        total = 0\n                        for child in nodes[nid]['children']:\n                            total += nodes[child]['sum']\n                        nodes[nid]['sum'] = total\n\n            propagate(root['parent'], nodes[node_id]['sum'] - old_sum)\n\n    return answer

Hints

Store each node's current subtree sum so a `get` query can be answered in O(1).
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.

Last updated: Apr 25, 2026

Loading coding console...