Convert a Binary Tree into a Sum Tree

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given a binary tree, convert it into a Sum Tree. In a Sum Tree, each node is assigned a new value which is the sum of the values of its left and right subtrees in the original tree. The value of a leaf node becomes 0 because it has no children. If the tree is empty, return null or handle it as a base case.

Examples❯

Input Tree Level Order Output Description
[10, -2, 6, 8, -4, null, 5]
[[13], [4, 5], [0, 0, 0]] Standard tree: Converted to sum tree where each node is the sum of values in its left and right subtrees
[1]
[[0]] Edge case: A single node becomes 0 as it has no children
[] [] Edge case: Empty tree
[5, 3, null, 2, null, null, null, 1]
[[6], [3], [1], [0]] Deep left-skewed tree converted into a sum tree; each node is updated recursively
[7, null, 9, null, null, null, 11]
[[20], [11], [0]] Right-skewed tree: Each node updated to sum of subtree

Solution❯

Case 1: Tree with Multiple Levels

In this case, the tree has several nodes and branches. Each internal node will be replaced with the sum of values from its left and right subtrees. For example, consider a node with left child 8 and right child -4 — its new value becomes 8 + (-4) = 4. Leaf nodes like 8 and -4 become 0 because they do not have children.

Case 2: Tree with a Single Node

If the binary tree contains only one node, it doesn't have any children. Therefore, when converting it into a sum tree, this single node will be assigned the value 0. There is no subtree to sum, so it becomes a leaf by default.

Case 3: Empty Tree

An empty tree has no nodes at all. There is nothing to convert. In this situation, the function should simply return null or an empty structure. This represents the base case in a recursive approach to solving the problem.

Algorithm Steps❯

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

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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