538. Convert BST to Greater Tree

MediumTreeDepth-First SearchBinary Search TreeBinary Tree

Problem Description

Given a Binary Search Tree (BST), the task is to transform it into a Greater Tree. In this new version of the tree, each node's value should be updated to be the sum of its original value plus the sum of all values of the nodes that have greater values in the BST. To clarify what constitutes a Binary Search Tree:

The left subtree of a node only contains nodes with keys less than the node's key.
The right subtree of a node only contains nodes with keys greater than the node's key.
Each left and right subtree must also be a binary search tree by itself.

Flowchart Walkthrough

Let's analyze LeetCode 538, Convert BST to Greater Tree, by navigating the Flowchart. Here are the steps according to the provided algorithm flowchart:

Is it a graph?

Yes: A binary search tree (BST) is a specialized form of a graph (tree), which is a type of acyclic graph.

Is it a tree?

Yes: More specifically, the BST is a tree where every node follows the ordering left < node < right.

Since it's a tree, we routinely look at Depth-First Search (DFS) as a preliminary approach to address problems involving tree traversal or manipulations.

Conclusion: The flowchart steers us towards the utilization of DFS to solve problems pertaining to tree data structures. This method is appropriate for traversing a BST in such a way that we can accumulate the sums of node values as required in the problem statement for Convert BST to Greater Tree. This problem essentially involves traversing the tree and updating each node's value based on those values that are greater than the current node, which is aptly handled by DFS.

Intuition

The intuition behind the solution comes from two properties of BSTs: in-order traversal and the properties of tree structure. By performing a reverse in-order traversal (visiting the right subtree first, then the current node, and then the left subtree), we can visit the nodes in decreasing order. As we traverse, we maintain a running sum of all the nodes visited so far. Since we're visiting nodes in decreasing order, this running sum is the sum of all the nodes greater than the current node.

Here's the step-by-step thinking:

Since a BST's in-order traversal yields sorted order, a reverse in-order traversal yields a sequence of nodes in non-increasing order.
Begin the reverse in-order traversal from the root with a running sum set to 0. This sum will be used to store the sum of all the nodes which are greater than the currently visited node.
For each node visited, add its value to the running sum. Then, update the current node's value to this running sum.
Proceed to the left subtree (which contains nodes with smaller values) and repeat the process.
By doing this, we've ensured that each node now contains the sum of its own value and all the nodes with greater value in the BST.

The solution provided uses a form of Morris Traversal (a tree traversal algorithm that doesn't use recursion or a stack) to achieve this without the extra space. Essentially, this algorithm makes use of the tree's leaf nodes' right children to create temporary links back to the node's ancestor (thereby avoiding the use of additional memory for traversal). Once done with the ancestor, these links are severed to revert the tree back to its original form.

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

Solution Approach

The provided solution uses the Morris Traversal technique, which is a clever way to traverse a binary tree without recursion and without a stack. This method takes advantages of the threaded binary trees concept, where a right NULL pointer is made to point to the inorder successor (if it exists).

Here is the breakdown of the Morris Traversal algorithm in the context of the problem:

Start from the root node of the BST and initialize a variable s to 0, which will keep track of the running sum of node values.
Iterate as long as the current node is not None.
Within the loop, check if the current node has a right child. If it does not have a right child, this means we are at the rightmost node (which is the largest). We update the running sum s by adding the current node’s value and then update the current node’s value to the new sum s. We then move to the left child of the current node.
If the current node has a right child, we will find the leftmost node of the right subtree (which is the inorder successor of the current node). We traverse to the right child of the current node and then keep moving to the left child until we find the leftmost node or until the left child is the current node itself.
If the leftmost node (inorder successor) does not have its left child set yet, we set it to point back to the current node and move to the right child of the current node to continue the traversal.
If the leftmost node already points back to the current node (creating a cycle), it means we have already visited this subtree. We reset the left child to None (breaking the cycle) which restores the tree structure. We then update the sum s and the current node’s value as described above, and move to the left child of the current node to continue the traversal.
Finally, when all nodes are visited in this reverse in-order manner, we end up with a tree where each node's value is equal to the original value plus the sum of all node values greater than itself. The original root of the BST is returned as the root of the Greater Tree.

By using Morris Traversal, the solution avoids additional space complexities that would come with using a stack for in-order traversal or recursion. Since the Morris Traversal is a constant space solution (O(1)), it proves to be an efficient way to resolve the problem at hand.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

To illustrate the Morris Traversal solution approach, let’s consider a simple BST and transform it into a Greater Tree according to the method described.

Let's take the following BST:

        5
       / \
      2   13

We start at the root (5). Since it has a right child (13), we'll find the inorder successor of 5.
The inorder successor of 5 is 13 since 13 has no left child. We create a temporary link from the rightmost node in 13's left subtree (which is 13 itself, as it doesn’t have a left subtree) back to 5.
We then visit the node 13, update the sum s = 0 + 13 = 13, and update 13's value with this sum. Now our tree looks as follows:

(The parentheses indicate a temporary link)

We go back to 5 via the temporary link and update it. The running sum s = 13 + 5 = 18, and we update 5's value with this sum:

        18
       /  \
      2    13

We then remove the temporary link from 13 to 5 and proceed to the left subtree of 5 (node 2).
Node 2 has no right child, so we update it directly. Running sum s = 18 + 2 = 20 and we update 2's value to 20:

        18
       /  \
     20    13

With no more nodes left to visit, the in-place transformation is complete and the original BST is now a Greater Tree:

        18
       /  \
     20    13

In this Greater Tree, each node's new value is the sum of its original value plus all values greater than it in the BST. The Morris Traversal allowed us to perform this transformation with O(1) additional space, respecting the constraints of the problem.

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 convertBST(self, root: TreeNode) -> TreeNode:
10        # This variable will keep a running sum of node values as we traverse the tree.
11        running_sum = 0
12        # `current` will point to the current node being processed.
13        current = root
14      
15        # Start Morris Traversal to convert the BST into a Greater Tree
16        while current:
17            # If there is no right child, process the current node and move to the left child.
18            if current.right is None:
19                running_sum += current.val
20                current.val = running_sum
21                current = current.left
22            else:
23                # Find the inorder predecessor of the current node
24                predecessor = current.right
25                while predecessor.left and predecessor.left != current:
26                    predecessor = predecessor.left
27              
28                # There is no left child to the predecessor, make current the left child of predecessor.
29                if predecessor.left is None:
30                    predecessor.left = current
31                    current = current.right
32                else:
33                    # Left child of predecessor exists which means we have processed right subtree.
34                    # Update the current node with the running sum.
35                    running_sum += current.val
36                    current.val = running_sum
37                    # Break the link to restore the tree structure.
38                    predecessor.left = None
39                    current = current.left
40      
41        # Return the modified tree.
42        return root
43

1class Solution {
2    // Convert the given BST to a Greater Tree where each key is changed to the original key plus
3    // the sum of all keys greater than the original key in the BST.
4    public TreeNode convertBST(TreeNode root) {
5        // Initialize the sum which will hold the total of all nodes visited so far.
6        int sum = 0;
7        TreeNode currentNode = root;
8      
9        // Iterate through the tree using a modified in-order traversal.
10        while (root != null) {
11            // If there is no right child, visit this node and traverse to its left child.
12            if (root.right == null) {
13                sum += root.val;
14                root.val = sum; // Update the value of the root with the sum.
15                root = root.left;
16            } else {
17                // Find the in-order predecessor of the root.
18                TreeNode predecessor = root.right;
19                while (predecessor.left != null && predecessor.left != root) {
20                    predecessor = predecessor.left;
21                }
22              
23                // If the left child of the predecessor is null, make the current root
24                // the left child of the predecessor and move to the right child of the root.
25                if (predecessor.left == null) {
26                    predecessor.left = root;
27                    root = root.right;
28                } else {
29                    // If the left child of the predecessor is the current root, update the
30                    // root's value with the sum and restore the original tree structure.
31                    sum += root.val;
32                    root.val = sum; // Update the value of the root with the sum.
33                    predecessor.left = null; // Restore the tree structure.
34                    root = root.left;
35                }
36            }
37        }
38      
39        // Return the reference to the node which is now the root of the modified tree.
40        return currentNode;
41    }
42}
43

1#include <iostream>
2
3struct TreeNode {
4    int val;
5    TreeNode *left;
6    TreeNode *right;
7    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11public:
12    TreeNode* convertBST(TreeNode* root) {
13        TreeNode* currentNode = root;
14        int sum = 0; // This will keep track of the sum of all nodes processed so far
15
16        // Iterate through the tree using Morris Traversal
17        while (currentNode) {
18            // If there is no right child, visit this node and go to its left child
19            if (!currentNode->right) {
20                sum += currentNode->val;
21                currentNode->val = sum; // Update the value of currentNode with the cumulative sum
22                currentNode = currentNode->left; // Move to the left child
23            } else {
24                // If there is a right child, find the leftmost child of the right subtree
25                TreeNode* rightSubtree = currentNode->right;
26                // Find the in-order predecessor of currentNode
27                while (rightSubtree->left && rightSubtree->left != currentNode) {
28                    rightSubtree = rightSubtree->left;
29                }
30                // Establish a temporary link from the in-order predecessor back to the currentNode
31                if (!rightSubtree->left) {
32                    rightSubtree->left = currentNode;
33                    currentNode = currentNode->right; // Move to the right child
34                } else {
35                    // We have a temporary link which indicates that we've visited the left subtree of currentNode
36                    sum += currentNode->val;
37                    currentNode->val = sum; // Update the currentNode with the sum
38                    rightSubtree->left = nullptr; // Remove the temporary link
39                    currentNode = currentNode->left; // Move to the left child
40                }
41            }
42        }
43        return root; // Return the modified tree
44    }
45};
46

1// Define a TreeNode class to represent tree nodes
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(x: number) {
8        this.val = x;
9        this.left = null;
10        this.right = null;
11    }
12}
13
14// Holds the current sum of all nodes processed so far
15let sum: number = 0;
16
17// Function to convert a binary search tree (BST) to a greater tree where every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST
18function convertBST(root: TreeNode | null): TreeNode | null {
19    let currentNode: TreeNode | null = root;
20
21    // Iterate through the tree using Morris Traversal
22    while (currentNode !== null) {
23        // If there is no right child, visit this node and go to its left child
24        if (currentNode.right === null) {
25            sum += currentNode.val;
26            currentNode.val = sum; // Update the value of the current node with the cumulative sum
27            currentNode = currentNode.left; // Move to the left child
28        } else {
29            // If there is a right child, find the leftmost child of the right subtree
30            let rightSubtree: TreeNode = currentNode.right;
31            // Find the in-order predecessor of the current node
32            while (rightSubtree.left !== null && rightSubtree.left !== currentNode) {
33                rightSubtree = rightSubtree.left;
34            }
35            // Establish a temporary link from the in-order predecessor back to the current node
36            if (rightSubtree.left === null) {
37                rightSubtree.left = currentNode;
38                currentNode = currentNode.right; // Move to the right child
39            } else {
40                // We have a temporary link which indicates that we've visited the left subtree of the current node
41                sum += currentNode.val;
42                currentNode.val = sum; // Update the current node with the sum
43                rightSubtree.left = null; // Remove the temporary link
44                currentNode = currentNode.left; // Move to the left child
45            }
46        }
47    }
48    return root; // Return the modified tree
49}
50
51// Example usage in TypeScript:
52// let tree: TreeNode = new TreeNode(2);
53// tree.left = new TreeNode(1);
54// tree.right = new TreeNode(3);
55// convertBST(tree);
56

Time and Space Complexity

The given code is a Morris traversal algorithm variant, which converts a Binary Search Tree (BST) into a Greater Tree such that the value of each node is replaced by the sum of all keys greater than the node key in BST.

Time Complexity

The time complexity of the algorithm is O(n), where n is the number of nodes in the BST. This is because each node is visited at most twice. Once while navigating rightward to establish the threaded links, and once while revisiting nodes to accumulate the sum and remove the threads.

Space Complexity

The space complexity of the algorithm is O(1) excluding the input and output space as the algorithm uses a constant amount of space for pointers and variables (s, node, next). It does not make any additional allocations and hence does not depend on the number of nodes in the tree - achieving in-place conversion.

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:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know