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

1038. Binary Search Tree to Greater Sum Tree

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)

DFS

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

For the current root node:

1. Sum the right subtree first, then get the updated sum from right subtree. rightSum
2. Update the current root node value to root.val + rightSum: root.val + rightSum
3. Sum the left subtree, then get the updated sum from left subtree: leftSum + root.val + rightSum
4. Return the updated sum from left subtree to parent.

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)

    // Add right sum to the current root node value
    root.`val` += rightSum

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

    // Why should we return leftSum? 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 leftSum
}

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)