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.

Transform tree with subtree sum mapping | Snowflake Coding Question

Quick Overview

Transform tree with subtree sum mapping evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Transform tree with subtree sum mapping

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given the roots of two complete binary trees T1 and T2 that have identical structure (same shape and number of nodes). Modify T2 so that, for every node position, the value stored at that node in T2 equals the sum of all node values in the corresponding subtree of T1 (including the root of that subtree). Implement transform(TreeNode t1, TreeNode t 2) to perform this in O(n) time, and state your space complexity. Describe the traversal order you use and how you map positions between the two trees. For testing, also implement buildCompleteTree(int[] levelOrder) that constructs a complete binary tree from a level-order array representation.

Quick Answer: Transform tree with subtree sum mapping evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given two complete binary trees, T1 and T2, that have identical structure (same shape and number of nodes). For testing convenience the trees are passed in level-order array form: index 0 is the root, and the node at index i has its left child at 2*i + 1 and its right child at 2*i + 2. Produce the new values for T2 so that, for every node position, the value equals the sum of all node values in the corresponding subtree of T1 (including that subtree's root). Implement `transform(t1, t2)` to return the transformed level-order array for T2 in O(n) time, and be ready to state the space complexity and traversal order you use. The array layout encodes a buildCompleteTree(levelOrder)-style representation: because the tree is complete and the two trees share structure, position i in T1 maps directly to position i in T2. Process indices from last to first so each parent can read its already-computed children's subtree sums. Example: T1 = [1, 2, 3, 4, 5, 6, 7], T2 = [10, 20, 30, 40, 50, 60, 70] -> [28, 11, 16, 4, 5, 6, 7] (root subtree sums to 28, left subtree of T1 sums to 2+4+5=11, right subtree sums to 3+6+7=16, leaves equal themselves).

Constraints

len(t1) == len(t2) (the two trees share identical structure)
0 <= n <= 10^5 nodes
Node values fit in a signed 32-bit / 64-bit integer; values may be negative
Children of index i are at 2*i + 1 and 2*i + 2 (level-order complete-tree layout)

Examples

Input: ([1, 2, 3, 4, 5, 6, 7], [10, 20, 30, 40, 50, 60, 70])

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

Explanation: Full 7-node tree: root = 1+2+3+4+5+6+7 = 28; left subtree = 2+4+5 = 11; right subtree = 3+6+7 = 16; the four leaves equal themselves.

Input: ([5], [99])

Expected Output: [5]

Explanation: Single node: its subtree is just itself, so the value becomes 5.

Input: ([], [])

Expected Output: []

Explanation: Empty tree edge case returns an empty array.

Input: ([1, 2, 3], [0, 0, 0])

Expected Output: [6, 2, 3]

Explanation: Root subtree sums to 1+2+3 = 6; the two leaves equal themselves.

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

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

Explanation: Incomplete last level (5 nodes): index 1 has children 3 and 4, so subtree(1) = -2 + -4 + -5 = -11; index 2 has no children, so subtree(2) = -3; root = -1 + -11 + -3 = -15. Confirms negative values and a non-full bottom level are handled.

Input: ([10, 20], [1, 1])

Expected Output: [30, 20]

Explanation: Two nodes: index 1 is the root's left child with no children, so it stays 20; root = 10 + 20 = 30.

Hints

Process node indices from the last position to the first. Because children always have a higher index than their parent in level-order, every child's subtree sum is finalized before its parent is reached.
subtree_sum[i] = t1[i] + (subtree_sum[2i+1] if it exists) + (subtree_sum[2i+2] if it exists). Guard the child indices against n.
Position i in T1 maps to position i in T2 because the trees are structurally identical, so you can write the result back to the same index. This is just a post-order traversal expressed over the array.

Quick Overview