algoadvance

Leetcode 538. Convert BST to Greater Tree

Problem Statement:

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that 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.

Clarifying Questions:

  1. Q: What is the structure of the node in the BST?
    • A: Each node contains an integer value, and it has references to its left and right children.
  2. Q: Is it possible to have negative values in the BST?
    • A: Yes, values in the BST can be negative.
  3. Q: Can the BST contain duplicate values?
    • A: Typically, a BST does not contain duplicate values.

Strategy:

To solve this problem, we can utilize the property of the BST along with a reverse in-order traversal (right -> root -> left). The reverse in-order traversal ensures that we process nodes in decreasing order of their values.

  1. Maintain a variable to keep track of the running sum of all the nodes processed so far.
  2. Traverse the tree in reverse in-order (i.e., visit the right subtree, then the node, and finally the left subtree).
  3. For each node, update its value by adding the running sum to its original value.
  4. Update the running sum for each visit by including the current node’s value.

This approach ensures each node gets the sum of all larger nodes added to it correctly.

Code:

Here’s the implementation of the strategy in C++:

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        convert(root, sum);
        return root;
    }

private:
    void convert(TreeNode* node, int &sum) {
        if (!node) return;
        convert(node->right, sum); // reverse in-order: right subtree
        sum += node->val;
        node->val = sum;
        convert(node->left, sum); // left subtree
    }
};

Time Complexity:

The time complexity of this solution is (O(n)), where (n) is the number of nodes in the BST. This is because we visit each node exactly once.

The space complexity is (O(h)), where (h) is the height of the BST. This accounts for the space used by the recursion stack, which, in the worst case (a completely unbalanced tree), would be proportional to the number of nodes (i.e., (O(n))). However, for a balanced tree, the space complexity would be (O(\log n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI