Convert Binary Tree into Sum Tree in Kotlin

by

To convert a binary tree into a sum tree, you can follow these steps:

  1. Traverse the binary tree in a bottom-up manner, starting from the leaf nodes.
  2. For each node, calculate the sum of the values of its left and right children, and store it in a variable.
  3. Replace the value of the current node with the sum calculated in step 2.
  4. Recursively repeat steps 2 and 3 for the parent of the current node until the root is reached.

Example :

Before conversion:
       10
      /  \
    -2    6
   / \    / \
  8  -4 7   5

After conversion:
       20
      /  \
     4    12
   / \    / \
  0   0 0   0

Implementation of the algorithm in Kotlin :

Kotlin
class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}
fun convertToSumTree(root: TreeNode?): Int {
    // Base case
    if (root == null) {
        return 0
    }    
    // Recursively convert left and right subtrees
    val leftSum = convertToSumTree(root.left)
    val rightSum = convertToSumTree(root.right)    
    // Store the original value of the current node
    val oldValue = root.`val`
    // Update the value of the current node to the sum of its left and right subtrees
    root.`val` = leftSum + rightSum    
    // Return the sum of the original value of the current node and the sum of its left and right subtrees
    return oldValue + root.`val`
}
fun main() {
    // Create a binary tree
    val root = TreeNode(10)
    root.left = TreeNode(-2)
    root.right = TreeNode(6)
    root.left?.left = TreeNode(8)
    root.left?.right = TreeNode(-4)
    root.right?.left = TreeNode(7)
    root.right?.right = TreeNode(5)
    // Convert the binary tree to a sum tree
    convertToSumTree(root)
    // Print the values of the nodes in the sum tree
    println(root.`val`) // Expected output: 20
    println(root.left?.`val`) // Expected output: 4
    println(root.right?.`val`) // Expected output: 12
}
  1. The function takes the root of the binary tree as an argument.
  2. The function checks if the current node is null. If it is, the function returns 0.
  3. The function recursively calls itself with the left child of the current node and stores the sum of its return value in leftSum.
  4. The function recursively calls itself with the right child of the current node and stores the sum of its return value in rightSum.
  5. The function stores the original value of the current node in oldValue.
  6. The function updates the value of the current node to the sum of leftSum and rightSum.
  7. The function returns the sum of oldValue and the new value of the current node.
  8. The parent node recursively receives the sum of its left and right children and updates its value.
  9. The function repeats steps 3 through 8 for the parent of the current node until the root is reached.

The time complexity of the convertToSumTree 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 binary tree exactly once.

The space complexity of the function is O(h), where h is the height of the binary tree. This is because the function uses the call stack to store information about each recursive call, and the maximum depth of the call stack is equal to the height of the binary tree. In the worst case, where the binary tree is skewed and has a height of n-1, the space complexity would be O(n). However, in a balanced binary tree, the height is logarithmic to the number of nodes, making the space complexity O(log n).

Leave a Comment