Transform tree using counterpart subtree sums
SnowflakeSoftware Engineer · Technical ScreenLast updated
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 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).
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.