Problem of The Day: Binary Search Tree to Greater Sum Tree

Problem Statement

Intuition

My first thought was to leverage an in-order traversal to accumulate the values of the nodes in a list. Then, by reversing this list, I could transform it into a format where I can easily compute the cumulative sums needed for converting a Binary Search Tree (BST) into a Greater Sum Tree (GST).

Approach

1. Traverse the tree in in-order and collect the nodes in a list.
2. Reverse the list to get the nodes in descending order.
3. Iterate through the reversed list and update each node’s value to be the sum of its value and all previously visited nodes’ values.

Complexity

• Time complexity: \(O(n)\) because we visit each node once during the traversal and the summing process.

• Space complexity: \(O(n)\) due to the extra space used for the list to store the nodes during the traversal.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        temp = []
        def helper(node):
            if not node:
                return
            helper(node.left)
            temp.append(node)
            helper(node.right)

        helper(root)
        temp.reverse()
        for i in range(1, len(temp)):
            temp[i].val += temp[i - 1].val
        return root

Editorial

Approach 1: In-order Traversal (Brute-Force)

class Solution:
    def bstToGst(self, root):
        # Store the inorder traversal in an array.
        self.inorder_traversal = []
        self.inorder(root)

        # Reverse the array to get descending order.
        self.inorder_traversal.reverse()

        # Modify the values in the tree.
        self.replace_values(root)

        return root

    def inorder(self, root):
        if root is None:
            return
        self.inorder(root.left)
        self.inorder_traversal.append(root.val)
        self.inorder(root.right)

    # Function to modify the values in the tree.
    def replace_values(self, root):
        if root is None:
            return
        self.replace_values(root.left)
        self.replace_values(root.right)

        # Replace node with values greater than the current value.
        node_sum = 0
        for i in self.inorder_traversal:
            if i > root.val:
                node_sum += i
            else:
                break

        root.val += node_sum

Approach 2: Reverse In-order Traversal

class Solution:
    def bstToGst(self, root):
        node_sum = [0]  # Using a list to emulate a mutable integer reference
        self.bst_to_gst_helper(root, node_sum)
        return root

    def bst_to_gst_helper(self, root, node_sum):
        # If root is null, make no changes.
        if root is None:
            return

        self.bst_to_gst_helper(root.right, node_sum)
        node_sum[0] += root.val
        # Update the value of root.
        root.val = node_sum[0]
        self.bst_to_gst_helper(root.left, node_sum)

Approach 3: Iterative Reverse In-order Traversal

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        node_sum = 0
        st = []
        node = root

        while st or node is not None:

            while node is not None:
                st.append(node)
                node = node.right
            # Store the top value of stack in node and pop it.
            node = st.pop()

            # Update value of node.
            node_sum += node.val
            node.val = node_sum

            # Move to the left child of node.
            node = node.left
        return root