[Algorithm] Elephant Tree (Tree/C++)

Problem Link: https://binarysearch.com/problems/Elephant-Tree.

This problem asks for returning the same tree but every node whose value is replaced by sum of its value and all its children’s value. This problem can be solved using recursion. As I mentioned in the other pose, do not just memorize the solutions but understand the thinking process and the logic behind the hood.

For those who are struggling to deal with recursion, try this thinking process that I frequently use.

Thinking Process

Goal: Make each node’s value = its value + sum of all nodes in the left subtree + sum of all nodes in the right subtree.

1. For a leaf node, its value would be its value + sum of left subtree + sum of right subtree but since it doesn’t have any subtree, it would be its value + 0 + 0.
2. Okay, we now know that the leaf node’s value should remain the same. This could be a good base condition.
3. To generalize, node->val = node->val + sum of left subtree + sum of right subtree
4. Let’s make dfs(Tree* node) a function which returns the sum of the current node’s value and all the children. Then,
5. node->val = node->val + dfs(node->left) + dfs(node->right)
6. Base condition: if(root==NULL) return 0;

Implementation