Leetcode 538. Convert BST to Greater Tree

Problem Explanation:

You are given a binary search tree (BST). You need to create and return a new binary tree such that each node value is equal to the original node's value plus the sum of all node values that were greater than the original node's value in the BST.

For Example:

1
2
3Input:   5
4        /   \
5       2     13
6
7Output: 18
8        /   \
9      20     13

Solution Approach:

A binary search tree is a tree data structure in which a node has at most two children known as the left child and the right child, and the left child node is always smaller than the parent node and the right child node is always greater than the parent node.

We can solve this problem by using the characteristics of the binary search tree and by traversing it in reverse order (first right, then parent and at last left), and keep on adding the values. This can be done by recursive depth-first search (DFS).

So, the approach will work as follow:

1. We will create a variable to keep the sum of the nodes.
2. Then we will traverse the nodes in reverse order by first visiting the right node.
3. We will add the current node value to the sum and make the sum equals to the current node value.
4. We will move to the left node and repeat the same process.
5. At last, we will return the root of the greater tree.

Python Solution:

1
2python
3class Solution:
4    def convertBST(self, root):
5        self.total = 0
6        
7        # post-order traverse right then left
8        def dfs(node):
9            if node:
10                dfs(node.right)
11                self.total += node.val
12                node.val = self.total
13                dfs(node.left)
14        
15        dfs(root)
16        return root

C++ Solution:

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

Java Solution:

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

JavaScript Solution:

1
2javascript
3class Solution {
4    convertBST(root) {
5        let total = 0;
6
7        let dfs = function(node) {
8            if (node) {
9                dfs(node.right);
10                total += node.val;
11                node.val = total;
12                dfs(node.left);
13            }
14        }
15
16        dfs(root);
17        return root;
18    }
19}

C# Solution:

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

The solution starts with the largest valued node (rightmost node) and move towards the smallest valued node (leftmost node), all the while keeping the track of sum of the processed nodes.## Rust Solution:

Since Rust doesn't officially support Object Oriented Programming and doesn't have null values, the solution would look a little different but the concept will remain the same.

1
2rust
3pub struct Solution;
4
5use std::cell::RefCell;
6use std::rc::Rc;
7
8impl Solution {
9    pub fn convert_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
10        fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, sum: &mut i32) {
11            if let Some(node) = node {
12                dfs(&node.borrow().right, sum);
13                *sum += node.borrow().val;
14                node.borrow_mut().val = *sum;
15                dfs(&node.borrow().left, sum);
16            }
17        }
18
19        let mut sum = 0;
20        dfs(&root, &mut sum);
21        root
22    }
23}

Swift Solution:

1
2swift
3class Solution {
4    private var total = 0
5
6    func convertBST(_ root: TreeNode?) -> TreeNode? {
7        if let root = root {
8            convertBST(root.right)
9            total += root.val
10            root.val = total
11            convertBST(root.left)
12        }
13        return root
14    }
15}

Kotlin Solution:

1
2kotlin
3class Solution {
4    private var total = 0
5
6    fun convertBST(root: TreeNode?): TreeNode? {
7        root?.let {
8            convertBST(root.right)
9            total += root.`val`
10            root.`val` = total
11            convertBST(root.left)
12        }
13        return root
14    }
15}

In the end, the time complexity of this solution is O(n), where n is the number of nodes in the BST. Since we are visiting each node once, the time complexity is proportional to the number of nodes. The space complexity is O(h), where h is the height of the tree, due to recursion stack. This is in the worst case where the tree is skewed, in an ideal balanced BST scenario the space complexity would be O(log n). The advantage of this approach is that we are making the use of the properties of a BST and using it to solve the problem in an efficient way. This is a good practice of how to traverse a tree and understanding the properties and nature of Binary Search Trees.