1038. Binary Search Tree to Greater Sum Tree

MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Problem Description

The given problem presents a Binary Search Tree (BST) and requires transforming it into a "Greater Tree." The transformation should be such that each node's value is updated to the sum of its original value and the values of all nodes with greater keys in the BST.

In a BST, the properties are as follows:

The left subtree of a node has nodes with keys less than the node's key.
The right subtree has nodes with keys greater than the node's key.
Both left and right subtrees adhere to the BST rules themselves.

The challenge lies in updating each node with the sum of values greater than itself while maintaining the inherent structure of the BST.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough to determine the appropriate algorithm for Leetcode 1038, Binary Search Tree to Greater Sum Tree:

Is it a graph?

Yes: Though specifically, it's a binary search tree (BST), which is a special kind of graph.

Is it a tree?

Yes: A binary search tree is indeed a tree.

Conclusion: For tree problems, the Depth-First Search (DFS) approach is generally useful to traverse or modify nodes due to the inherent hierarchical structure of the tree. In this problem, DFS can be utilized to traverse the tree in reverse in-order (right, node, left) to accumulate values and update each node to the greater sum. Thus, the flowchart leads us to use DFS for this problem.

Intuition

The solution approach leverages the properties of the BST, specifically the in-order traversal property where visiting nodes in this order will access the nodes' values in a sorted ascending sequence. However, to obtain a sum of the nodes greater than the current node, we need to process the nodes in the reverse of in-order traversal, which means we should begin from the rightmost node (the highest value) and traverse to the leftmost node (the lowest value).

We'll maintain a running sum s that accumulates the values of all nodes visited so far during our reverse in-order traversal. For each node n, we will:

Recursively visit the right subtree to add all greater values to s.
Update n's value by adding s to n's original value.
Add n's updated value (which is inclusive of its original value) to s before moving to the left subtree.

This process ensures that each node's value is replaced by the sum of its original value and all greater values in the BST. Our solution does this iteratively with the help of a Morris traversal-like algorithm that reduces the space complexity to O(1) by temporarily modifying the tree structure during traversal and then restoring it before moving to the left subtree.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The solution provided utilizes an iterative approach with a Morris traversal pattern, which aims to traverse the tree without additional space for recursion or a stack. Morris traversal takes advantage of the thread, a temporary link from a node to its predecessor, to iterate through the tree. Here's the breakdown of the approach:

Initialize a variable s to store the running sum and a variable node to keep the reference of the original root.
Start iterating from the root of the BST. Continue until the root is not null, as this indicates the traversal is complete.
For each node, there are two cases to consider:
- If there is no right child, add the node's value to s. Then, update the node's value with s and move to the left child.
- If there is a right child, find the leftmost child of this right subtree (next), which will act as the current node's predecessor.
If the leftmost child (next) doesn't have a left child (indicating that we haven't processed this subtree yet), make the current node its left child (creating a thread) and move to the right child of the current node, deferring its update until after the greater values have been incorporated into s.
If the leftmost child (next) already has a left child (meaning the current node has been threaded and it’s time to update it), remove the thread, add the current node's value to s, update the current node's value with s, and move to the left child.
The loop continues until all nodes have been visited in reverse in-order, which updates all nodes with the sum of all greater node values.

This Morris traversal-based algorithm effectively improves space complexity to O(1) as it doesn't use any auxiliary data structure. The time complexity remains O(n), where 'n' is the number of nodes in the BST since each node is visited at most twice.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution with a simple BST example:

Consider a BST with the following structure:

      4
     / \
    1   6

We want to transform it into a "Greater Tree" using the described Morris Traversal approach.

We start with the root node which has the value 4. We initialize s to 0.
Since node 4 has a right child (6), we look for the leftmost node in node 4's right subtree. Node 6 has no left child, so this step is skipped.
Since node 6 has no right child, we process it by adding its value to s. Now s = 0 + 6 = 6 and update node 6 to the new value s. The BST now looks like this:

      4
     / \
    1   6

Node 6 has been transformed into a "Greater Node" containing the sum of values greater than itself (which in this simple case is just its own value because it's the highest).

Returning to node 4, we now should add its value to s (s = 6 + 4 = 10) and update it to the new value s. The tree structure at this moment is:

      10
     / \
    1   6

Node 4 is now a "Greater Node" having the sum of all nodes greater than itself.

Now we consider the left child of node 4, which is node 1. Since node 1 does not have a right child, we add its value to s (s = 10 + 1 = 11) and update its value:

      10
     / \
    11  6

Node 1 is now a "Greater Node," which includes the sum of all nodes greater than it.

Since node 1 is the leftmost node and it has no left child, our traversal and the transformation are complete for this simple tree.

The final "Greater Tree" is:

      10
     / \
    11  6

Followed by the Morris Traversal approach discussed, each node's value has been updated with the sum of all greater node values while maintaining the BST structure.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def bstToGst(self, root: TreeNode) -> TreeNode:
10        total_sum = 0  # This will store the running sum of nodes
11      
12        # Start with the root node
13        current_node = root
14      
15        # Traverse the tree
16        while current_node:
17          
18            # If there is no right child, update the current node's value with total_sum
19            # and move to the left child
20            if current_node.right is None:
21                total_sum += current_node.val
22                current_node.val = total_sum
23                current_node = current_node.left
24            else:
25                # If the right child is present, find the leftmost child in the right subtree
26                predecessor = current_node.right
27                while predecessor.left and predecessor.left != current_node:
28                    predecessor = predecessor.left
29                  
30                # Establish a temporary link between current_node and its predecessor
31                if predecessor.left is None:
32                    predecessor.left = current_node
33                    current_node = current_node.right
34                else:
35                    # When leftmost child is found and a cycle is detected (temporary link exists),
36                    # revert the changed tree structure and update the current node
37                    total_sum += current_node.val
38                    current_node.val = total_sum
39                    predecessor.left = None
40                    current_node = current_node.left
41      
42        # Return the modified tree
43        return root
44

1class Solution {
2    public TreeNode bstToGst(TreeNode root) {
3        int sum = 0; // This variable keeps track of the accumulated sum
4        TreeNode currentNode = root; // Save the original root to return the modified tree later
5
6        // Iteratively traverse the tree using the reverse in-order traversal
7        // (right -> node -> left) because this order visits nodes from the largest to smallest
8        while (root != null) {
9            // If there is no right child, update the current node's value with the sum and go left
10            if (root.right == null) {
11                sum += root.val; // Accumulate the node's value into sum
12                root.val = sum; // Update the node's value with the accumulated sum
13                root = root.left; // Move to the left child
14            } else {
15                // Find the inorder successor, the smallest node in the right subtree
16                TreeNode inorderSuccessor = root.right;
17                // Keep going left on the successor until we reach the bottom left most node
18                // that is not the current root
19                while (inorderSuccessor.left != null && inorderSuccessor.left != root) {
20                    inorderSuccessor = inorderSuccessor.left;
21                }
22
23                // When we find the leftmost child of the inorder successor
24                if (inorderSuccessor.left == null) {
25                    // Set a temporary link back to the current root node and move to the right child
26                    inorderSuccessor.left = root;
27                    root = root.right;
28                } else {
29                    // The temporary link already exists, and we've visited the right subtree
30                    sum += root.val; // Update the sum with the current value
31                    root.val = sum; // Update current root's value with accumulated sum
32                    inorderSuccessor.left = null; // Remove the temporary link
33                    root = root.left; // Move to the left child
34                }
35            }
36        }
37        // Return the modified tree starting from the original root node
38        return currentNode;
39    }
40}
41

1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10};
11
12class Solution {
13public:
14    TreeNode* bstToGst(TreeNode* root) {
15        int sum = 0; // Initialize sum to keep track of the accumulated values.
16        TreeNode* node = root; // Keep track of the original root node
17      
18        // Traverse the tree.
19        while (root != nullptr) {
20            // If there is no right child, process current node and move to left child.
21            if (root->right == nullptr) {
22                sum += root->val;
23                root->val = sum; // Update the value to be the greater sum.
24                root = root->left;
25            } else {
26                // Find the in-order predecessor of the current node.
27                TreeNode* predecessor = root->right;
28                while (predecessor->left != nullptr && predecessor->left != root) {
29                    predecessor = predecessor->left;
30                }
31              
32                // If the left child of the predecessor is null, set it to the current node.
33                if (predecessor->left == nullptr) {
34                    predecessor->left = root;
35                    root = root->right; // Move to the right child.
36                } else {
37                    // If the left child of the predecessor is the current node, process current node.
38                    sum += root->val;
39                    root->val = sum; // Update the node's value to be the greater sum.
40                  
41                    // Restore the tree structure by removing the temporary link.
42                    predecessor->left = nullptr;
43                    root = root->left; // Move to the left child.
44                }
45            }
46        }
47        // Return the modified tree which now represents the Greater Sum Tree.
48        return node;
49    }
50};
51

1// Function to transform a Binary Search Tree into a Greater Sum Tree
2function bstToGst(root: TreeNode | null): TreeNode | null {
3    let current = root;
4    let totalSum = 0;
5  
6    // Loop over the tree using Morris Traversal approach
7    while (current != null) {
8        let rightNode = current.right;
9      
10        // Case where there is no right child
11        if (rightNode == null) {
12            totalSum += current.val;       // Update the total sum with current value
13            current.val = totalSum;        // Modify the current node's value to total sum
14            current = current.left;        // Move to the left subtree
15        } else {
16            // Find the leftmost node in the current's right subtree
17            let leftMost = rightNode;
18            while (leftMost.left != null && leftMost.left != current) {
19                leftMost = leftMost.left;
20            }
21          
22            // First time visiting this right subtree, make a thread back to current
23            if (leftMost.left == null) {
24                leftMost.left = current;
25                current = rightNode;
26            } else {  // Second time visiting - the thread is already there
27                leftMost.left = null;     // Remove the thread
28                totalSum += current.val;  // Update the total sum with current value
29                current.val = totalSum;   // Modify the current node's value to the total sum
30                current = current.left;   // Move to the left subtree
31            }
32        }
33    }
34  
35    // Return the modified tree root
36    return root;
37}
38

Time and Space Complexity

The provided code implements a variation of the Morris traversal algorithm to convert a Binary Search Tree (BST) to a Greater Sum Tree (GST), where every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

Time Complexity

The time complexity of the code is O(n), where n is the number of nodes in the tree. This is because each node is visited at most twice—once when the right child is connected to the current node during the transformation to threaded trees and once when it is reverted. There is no recursion stack or separate data structure which keeps track of the visited nodes. The while loop and nested while loop both ensure that each node is processed.

Space Complexity

The space complexity of the code is O(1) if we do not consider the space required for the output structure - it modifies the tree nodes in place with a constant number of pointers. There is no use of recursion, nor is there any allocation of proportional size to the number of nodes. However, if the function call stack is taken into account then that will not increase our space complexity because the recursion stack is not being used here. The operation is done by manipulating the right pointers of the original tree.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don’t know