Transform tree using counterpart subtree sums
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given the roots of two complete binary trees with identical structure, modify the node values of the second tree so that each node equals the sum of all node values in the subtree rooted at the same position in the first tree (including that corresponding root). Provide an algorithm that runs in linear time relative to the number of nodes and uses at most O(h) extra space, where h is tree height. Describe recursion vs. iteration choices, how you verify shape identity, and how you would test edge cases (single node, skewed last level, large values).
Quick Answer: This question evaluates proficiency with binary tree algorithms and in-place subtree aggregation, emphasizing traversal strategies, shape verification, and handling subtree sums under linear-time and O(h) space constraints.
Given identical complete-tree arrays, replace each second-tree node with the subtree sum at the same position in the first tree.
Constraints
- Trees have identical array shape
Examples
Input: ([1, 2, 3], [0, 0, 0])
Expected Output: [6, 2, 3]
Explanation: Root sum and leaf sums.
Input: ([5], [9])
Expected Output: [5]
Explanation: Single node.
Input: ([1, 2, 3, 4, 5, 6, 7], [0, 0, 0, 0, 0, 0, 0])
Expected Output: [28, 11, 16, 4, 5, 6, 7]
Explanation: Full tree.
Hints
- Postorder traversal computes each subtree sum once.