Katkat

Transform tree with subtree sum mapping

SnowflakeSoftware Engineer · Technical Screen

Last updated

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