Trees and Graphs‎ > ‎

Subtree Sum

Given a binary tree, write a method that resets the values of all non-leaf nodes to the sum of their subtree nodes.

void SubtreeSum(Node *n)
{
    // Base case - don't touch the leaf nodes
    if (!n || (!n->left && !n->right))
        return;
 
    // Post-order traversal
    SubtreeSum(n->left);
    SubtreeSum(n->right);
 
    n->value = 0;
    if (n->left)
        n->value += n->left->value;
    if (n->right)
        n->value += n->right->value;
}