Coding - Rewrite Tree With Subtree Sums

The "Rewrite Tree With Subtree Sums" interview question, often associated with companies like xAI and Snowflake, requires transforming a binary tree into a "Sum Tree" where each node's value is replaced by the sum of all elements in its left and right subtrees.

Problem Statement

Given the root of a binary tree, modify the tree in-place so that every node contains the sum of all nodes in its original left and right subtrees. Naukri.com +1

Key Constraints & Definitions:

• Leaf Nodes: The value of a leaf node becomes 000 because it has no subtrees.
• Subtree Sum: For any node, the new value is 𝑆𝑢𝑚(Left Subtree)+𝑆𝑢𝑚(Right Subtree), where these sums refer to the original values of the nodes in those subtrees.
• Return Value: Typically, the function modifies the tree in-place and may return the total sum of the original tree to assist with recursive calculations. YouTube +2

Example

Input Tree:

`text 10 /
-2 6 / \ /
8 -4 7 5

`

Output Tree (after rewriting):

`text 20 (8-4 + 7+5) /
4 12 (7+5) / \ /
0 0 0 0

`

Recommended Approach

The most efficient way to solve this is using a post-order traversal (Left, Right, Root). Naukri.com +1

1. Base Case: If the node is null, return 000.
2. • Recursively calculate the sum of the left subtree.
   • Recursively calculate the sum of the right subtree.
3. Recursively calculate the sum of the left subtree.
4. Recursively calculate the sum of the right subtree.
5. • Store the node's original value (to return to the parent).
   • Set the node's new value to leftSum + rightSum.
6. Store the node's original value (to return to the parent).
7. Set the node's new value to leftSum + rightSum.
8. Return: Return the oldValue + leftSum + rightSum so the parent can calculate its own subtree sum. Naukri.com +1

Would you like to see a Python or C++ implementation of this recursive solution?

[0] - 53 Binary Tree Interview Questions (With Sample Answers) - Indeed [1] - Convert a binary tree to its sum tree - Naukri Code 360 [2] - POTD- 08/08/2024 | Sum Tree | Problem of the Day ... [3] - Change a Binary Tree so that every node stores sum of all nodes in left ... [4] - Rewrite Tree With Subtree Sums | 1Point3Acres