Leetcode 1038. Binary Search Tree to Greater Sum Tree

Problem Explanation

Given a root node of a binary search tree, we are asked to modify the tree such that each node's new value is equal to the sum of all the values in the original tree that are greater than or equal to the current node's value.

For instance, given the binary search tree:

1
2
3    4
4   / \
5  1   6
6 / \ / \
70  2 5  7

When traversed in reverse order (right -> node -> left), the nodes are processed from the biggest to the smallest: 7, 6, 5, 4, 2, 1, 0. The sum of all these numbers is 7 + 6 + 5 + 4 + 2 + 1 + 0 which equals 25. As we process each node, we keep the running sum. At each node, we replace its value with our running sum.

Transforming the tree using this approach results in:

1
2
3    30
4   /  \
5  36   21
6 /  \ /  \
736 35 26  15

The solution approach entails conducting a reversed in-order traversal of the binary search tree and updating the node values as the sum of values greater than or equal to the current node's value. The reversed inorder traversal is performed as follows: we first traverse the right subtree, visit the node, and then traverse the left subtree.

Python Solution

1
2python
3class Solution:
4    def bstToGst(self, root: TreeNode) -> TreeNode:
5        
6        def reverse_inorder(node):
7            nonlocal total
8            if node:
9                # first recurse on the right child
10                reverse_inorder(node.right)
11                # update the total and the current node's value
12                total += node.val
13                node.val = total
14                # recurse on the left child
15                reverse_inorder(node.left)
16        
17        total = 0
18        reverse_inorder(root)
19        
20        return root

Java Solution

1
2java
3class Solution {
4    int sum = 0;
5    public TreeNode bstToGst(TreeNode root) {
6        if(root != null){
7            bstToGst(root.right);
8            sum += root.val;
9            root.val = sum;
10            bstToGst(root.left);
11        }
12        return root;
13    }
14}

JavaScript Solution

1
2javascript
3var bstToGst = function(root) {
4    var sum = 0;
5    function reverse_inorder(node){
6        if(node){
7            reverse_inorder(node.right);
8            sum += node.val;
9            node.val = sum;
10            reverse_inorder(node.left);
11        }
12    }
13    reverse_inorder(root);
14    return root;
15};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int sum = 0;
6    TreeNode* bstToGst(TreeNode* root) {
7        if (root) {
8            bstToGst(root->right);
9            sum += root->val;
10            root->val = sum;
11            bstToGst(root->left);
12        }
13        return root;
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    int total = 0;
5    public TreeNode BstToGst(TreeNode root) {
6        if (root != null) {
7            BstToGst(root.right);
8            total += root.val;
9            root.val = total;
10            BstToGst(root.left);
11        }
12        return root;
13    }
14}

In all the solutions above, we use a reversed inorder DFS traversal to aggregate a running sum of all values in the binary search tree. We started by traversing the right subtree which contains larger values, then the current node, before traversing the left subtree which contains smaller values. The current node value is replaced by the sum of its value and all the previous sums. This ensures that each node's new value is equal to the sum of the values in the original tree that are greater than or equal to node.val.In Python, the nonlocal keyword is used to allow an inner function to access a variable from an outer function. In other languages, like Java, JavaScript, and C++, which do not support the nonlocal keyword, you can use an instance variable to achieve the same result.

The time complexity of these solutions is O(N), where N is the number of nodes in the binary search tree. This is because we visit each node exactly once.

The space complexity is also O(N), or more precisely it's O(H), where H is the height of the binary search tree. This is due to the space required by the call stack for the recursive traversal. In a worst-case scenario, the tree is completely unbalanced, such as when each node only contains a left or right child node, causing a recursive call to be made for each node in the tree, so H equals N. In the best case, the tree is perfectly balanced, so H = log(N).

To conclude, the strategy of using a reverse in-order traversal to solve this problem is a great example of using knowledge of data structures' properties (in this case, the properties of a binary search tree) in order to conceive an efficient solution strategy. Similar problems where a specific traversal method helps simplify a problem are common in coding interviews, so getting comfortable with these techniques can be very beneficial.