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