Convert a Binary Tree into a Sum Tree

Algorithm Steps

If the tree is empty, return 0.
Recursively convert the left subtree into a sum tree and obtain its sum.
Recursively convert the right subtree into a sum tree and obtain its sum.
Store the current node's original value in a temporary variable, e.g., oldVal.
Update the current node's value to the sum of the left and right subtree sums.
Return the sum of the updated node value and the original value (node.val + oldVal) so it can be used by the parent node.

Convert a Binary Tree into a Sum Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def toSumTree(root):
    if root is None:
        return 0
    old_val = root.val
    left_sum = toSumTree(root.left)
    right_sum = toSumTree(root.right)
    root.val = left_sum + right_sum
    return root.val + old_val

# Example usage:
if __name__ == '__main__':
    # Construct the binary tree:
    #         10
    #        /  \
    #      -2    6
    #      / \   
    #     8  -4  
    root = TreeNode(10, TreeNode(-2, TreeNode(8), TreeNode(-4)), TreeNode(6))
    toSumTree(root)
    # The tree is now converted into a sum tree