1038.binary-search-tree-to-greater-sum-tree.md

1038. Binary Search Tree to Greater Sum Tree

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

• The greater value of the node comes from parent node. Or the smaller value of the node goes to parent node.

         4(23)
           \
            6(14)
           /    \   
          5(19)  8(8)


        4(4)
       /
      1(10)
       \
        2(9)
          \
           3(7)

Approach

We only think about what to do in current root node, other nodes are handled by recursion. For the current root node:

1. It will receive the sum of all nodes greater than itself. (The parameter of our recursive function)
2. We convert the right child to a greater sum tree in bottom-up manner.
3. After conver the right child, we will get the sum of all nodes greater than the right child. rightSum.
4. We update the current root node value to root.val + rightSum.
5. We convert the left child to a greater sum tree in top-down manner with root.val + rightSum as the parameter.
6. Return the sum of root node and all its children as the next greater sum.

fun bstToGst(root: TreeNode?): TreeNode? {
    if (root == null) return null
    build(root, 0)
    return root
}

private fun build(root: TreeNode?, value: Int): Int {
    // If the root is null, return the value, not 0. It indicates that we
    // don't update the value of the current node.
    if (root == null) return value

    // Build right child from bottom up approach
    //     4(4)
    //    /
    //   1
    //    \
    //     2
    //      \
    //       3(7) We have to pass value 4 to node 3.
    var rightSum = build(root.right, value)

    // We update from the result of right child
    var currentSum = root.`val` + rightSum
    root.`val` = currentSum

    // Build left child from top down approach with new sum
    currentSum = build(root.left, currentSum)

    // Why should we return currentSum? Because we need to return the sum of
    // the current node and all its children. Not just the current node.
    // For example, the tree below:
    //   4 
    //    \
    //     6(14) // here we should return 19 to the parent node (4)., not 14.
    //   /     \
    //  5(19)  8(8)
    //
    // Root 4 will receive 19, not 14. Because 21 is the sum of 5, 6, 8.
    return currentSum
}

Or equivalently, we can maintain a global variable to store the sum.

private var sum = 0
  fun bstToGst(root: TreeNode?): TreeNode? {
      inorder(root)
      return root
  }

  private fun inorder(root: TreeNode?) {
      if (root == null) return
      // We traverse the right subtree first, then the root, and then the left subtree.
      
      inorder(root.right)
      sum += root.`val`
      root.`val` = sum
      inorder(root.left)
  }

• Time Complexity: O(n), where n is the number of nodes in the tree.
• Space Complexity: O(h)