D
DevExCode

LeetCode 538: Convert BST to Greater Tree Solution

Master LeetCode problem 538 (Convert BST to Greater Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

538. Convert BST to Greater Tree

Medium
TreeDepth-First SearchBinary Search TreeBinary Tree

Problem Explanation

Explanation

To convert a Binary Search Tree (BST) to a Greater Tree, we can perform a reverse in-order traversal of the tree. In a reverse in-order traversal, we visit nodes in the right subtree first, followed by the current node, and then the left subtree. During this traversal, we keep track of the running sum of nodes visited so far. At each node, we update its value by adding the running sum to it.

Algorithm:

  1. Initialize a variable sum to keep track of the running sum.
  2. Perform a reverse in-order traversal of the BST.
  3. For each node visited:
    • Update the node's value by adding sum to it.
    • Update sum by adding the node's value to it.
  4. Return the modified root of the BST.

Time Complexity: O(n) - where n is the number of nodes in the BST. Space Complexity: O(h) - where h is the height of the BST.

Solution Code

class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 538 (Convert BST to Greater Tree)?

This page provides optimized solutions for LeetCode problem 538 (Convert BST to Greater Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 538 (Convert BST to Greater Tree)?

The time complexity for LeetCode 538 (Convert BST to Greater Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 538 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 538 in Java, C++, or Python.

Back to LeetCode Solutions