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 Technical Screen rounds at Snowflake.

What role is this question designed for?

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

Set second tree values by subtree sums | Snowflake Coding Question

Set second tree values by subtree sums

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given the roots of two complete binary trees T1 and T2 that have identical structure and the same number of nodes, replace each value in T2 with the sum of all node values in the corresponding subtree of T1 (including the matching root of that subtree). Implement: ( 1) a function that performs this transformation in O(n) time and O(h) extra space, where n is the number of nodes and h is tree height; ( 2) helpers to build a complete binary tree from a level-order array (use null for missing children) and to serialize a tree back to an array for testing. State assumptions and handle edge cases like empty trees, negative values, and integer overflow.

Quick Answer: This question evaluates a candidate's competence in binary tree data structures and algorithmic efficiency, focusing on tree traversal techniques, subtree aggregation, and handling robustness aspects such as empty trees and integer overflow.

You are given two complete binary trees T1 and T2 that have **identical structure** (same number of nodes, same shape). Replace each value in T2 with the **sum of all node values in the corresponding subtree of T1** (including the matching root of that subtree). Because T1 and T2 share the same structure, the transformed values of T2 are fully determined by T1. To make the challenge self-contained and testable, your function works directly with the array representation: - **Input:** `t1_level_order` — a level-order array describing T1, using `null`/`None` for missing children. - **Output:** an array in the **same level-order layout** where every present node holds the subtree sum of the corresponding T1 node, and missing positions stay `null`/`None`. This array is exactly the level-order serialization of the transformed T2. You must (1) build the tree from the level-order array, (2) compute each node's subtree sum in O(n) time and O(h) extra space (h = tree height), and (3) serialize the result back to the array layout. **Edge cases to handle:** empty tree (`[]`), a single node, negative values, and sparse trees where some internal nodes have only one child (encoded with `null`). Subtree sums can grow large, so use a 64-bit integer type in Java/C++ to avoid overflow. **Example:** for the perfect tree `[1, 2, 3, 4, 5, 6, 7]`, the root's subtree sum is `1+2+3+4+5+6+7 = 28`, node `2`'s subtree is `2+4+5 = 11`, node `3`'s subtree is `3+6+7 = 16`, and the leaves keep their own values, giving `[28, 11, 16, 4, 5, 6, 7]`.

Constraints

0 <= n <= 10^5 nodes
Node values fit in a 32-bit signed integer; subtree sums may exceed 32 bits, so use a 64-bit type (long / long long) for accumulation.
The input array is a valid level-order encoding of a binary tree (null marks a missing child).
T1 and T2 are guaranteed to have identical structure.

Examples

Input: ([1, 2, 3, 4, 5, 6, 7],)

Expected Output: [28, 11, 16, 4, 5, 6, 7]

Explanation: Perfect tree. Root subtree = 1+2+3+4+5+6+7 = 28; node 2's subtree = 2+4+5 = 11; node 3's subtree = 3+6+7 = 16; leaves keep their own values.

Input: ([5],)

Expected Output: [5]

Explanation: Single node: its subtree sum is just itself.

Input: ([],)

Expected Output: []

Explanation: Empty tree edge case returns an empty array.

Input: ([10, -3, 8],)

Expected Output: [15, -3, 8]

Explanation: Negative values handled: root subtree = 10 + (-3) + 8 = 15; the two leaves keep their own values.

Input: ([1, 2, 3, None, None, 4, 5],)

Expected Output: [15, 2, 12, None, None, 4, 5]

Explanation: Sparse tree: node 2 is a leaf (children are null), so it stays 2; node 3's subtree = 3+4+5 = 12; root = 1+2+3+4+5 = 15. Null positions are preserved.

Input: ([-1, -2, -3, -4, -5],)

Expected Output: [-15, -11, -3, -4, -5]

Explanation: All-negative tree: node -2's subtree = -2+(-4)+(-5) = -11; node -3 is a leaf = -3; root = sum of all = -15.

Hints

You don't need T2's values at all — since T1 and T2 share structure, T2's new values are entirely determined by T1's subtree sums.
Build the tree from the level-order array with a BFS queue: pop a node, attach its next two array entries as left/right children (skipping nulls).
Compute subtree sums with a post-order traversal so each node sees its children's sums before its own. An explicit stack keeps extra space at O(h) instead of relying on recursion.
When serializing back, walk the same BFS order you used to build the tree and emit null wherever the original array had null, so the output layout matches the input exactly.

Quick Overview

This question evaluates a candidate's competence in binary tree data structures and algorithmic efficiency, focusing on tree traversal techniques, subtree aggregation, and handling robustness aspects such as empty trees and integer overflow.