Check if a Binary Tree is a Sum Tree

Algorithm Steps

If the tree is empty, return true with sum = 0.
If the node is a leaf, return true with sum equal to the node's value.
Recursively check the left and right subtrees to obtain their sums and whether they are sum trees.
For the current node, verify that it is a sum tree by checking if its value equals the sum of the left and right subtree sums.
Return true for the current node if both subtrees are sum trees and the node's value equals the left sum plus the right sum; also, return the total sum (node's value + left sum + right sum).
If the condition fails, return false.

Check if a Binary Tree is 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 isSumTree(root):
    # Returns a tuple (isSumTree, sum)
    if root is None:
        return (True, 0)
    if root.left is None and root.right is None:
        return (True, root.val)
    leftIsSum, leftSum = isSumTree(root.left)
    rightIsSum, rightSum = isSumTree(root.right)
    total = leftSum + rightSum
    if leftIsSum and rightIsSum and root.val == total:
        return (True, root.val + total)
    else:
        return (False, 0)

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         26
    #        /  \
    #      10    3
    #     /  \    \
    #    4    6    3
    root = TreeNode(26, TreeNode(10, TreeNode(4), TreeNode(6)), TreeNode(3, None, TreeNode(3)))
    print(isSumTree(root)[0])