Check if Binary tree is a Sum Tree in Kotlin

A binary tree is considered a sum tree if the value of each node is equal to the sum of the values of its left and right subtrees. To check if a binary tree is a sum tree, we can use a recursive function that checks the sum property for each node.

Here’s the algorithm:

1. Define a function isSumTree that takes a TreeNode object as its input and returns a boolean value.
2. Check if the input node is null. If it is, return true.
3. Check if the input node is a leaf node (i.e., it has no children). If it is, return true.
4. Recursively call the isSumTree function with the left subtree of the input node as its argument. If the function returns false, return false from the current call.
5. Recursively call the isSumTree function with the right subtree of the input node as its argument. If the function returns false, return false from the current call.
6. Calculate the sum of the values of the left and right subtrees of the input node. If the sum is equal to the value of the input node, return true. Otherwise, return false.

Example of Sum Tree :

            26
           /  \
         10    3
        /  \     \
       4    6    3

Here’s an implementation of the isSumTree function in Kotlin:

data class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)
fun isSumTree(root: TreeNode?): Boolean {
    if (root == null) {
        return true
    }
    if (root.left == null && root.right == null) {
        return true
    }
    val leftNode = root.left
    val rightNode = root.right
    val leftSum = if (leftNode != null) {
        if (leftNode.left == null && leftNode.right == null) {
            leftNode.value
        } else {
            2 * leftNode.value
        }
    } else {
        0
    }
    val rightSum = if (rightNode != null) {
        if (rightNode.left == null && rightNode.right == null) {
            rightNode.value
        } else {
            2 * rightNode.value
        }
    } else {
        0
    }
    return root.value == leftSum + rightSum && isSumTree(leftNode) && isSumTree(rightNode)
}
fun main() {
    // Construct the binary tree
    val root = TreeNode(26)
    root.left = TreeNode(10)
    root.right = TreeNode(3)
    root.left?.left = TreeNode(4)
    root.left?.right = TreeNode(6)
    root.right?.right = TreeNode(3)

    // Check if the binary tree is a sum tree
    if (isSumTree(root)) {
        println("The binary tree is a sum tree")
    } else {
        println("The binary tree is not a sum tree")
    }
}

1. The isSumTree function takes a root node of a binary tree as input.
2. If the root node is null, then the function returns true. This is because an empty tree is considered a valid sum tree.
3. If the root node is a leaf node (i.e. it has no children), then the function returns true. This is because a single node is considered a valid sum tree.
4. The function recursively checks if the left and right subtrees of the root node are sum trees. This is done by calling the isSumTree function recursively with the left and right child nodes as input.
5. If both the left and right subtrees are sum trees, then the function checks if the sum of their values is equal to the value of the root node. If this condition is true, then the function returns true. Otherwise, it returns false.
6. If either the left or right subtree is not a sum tree, then the function returns false. This is because the sum property of a sum tree is violated if any subtree is not a sum tree.

The time complexity of the isSumTree function is O(n), where n is the number of nodes in the binary tree. This is because the function recursively visits each node in the tree once, and performs a constant amount of work at each node.

The space complexity of the function is also O(n), where n is the number of nodes in the binary tree. This is because the function uses the call stack to recursively visit each node in the tree, and the maximum depth of the call stack is equal to the height of the tree. In the worst case, the binary tree could be a degenerate tree with all nodes in a single chain, so the height of the tree would be n and the space complexity would be O(n).