> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/data-structure/tree/538-convert-bst-to-greater-tree.md).

# 538 Convert BST to Greater Tree

## 538. Convert BST to Greater Tree

## 1. Question

Given 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 sum of all keys greater than the original key in BST.

**Example:**

```
Input:
 The root of a Binary Search Tree like this:
              5
            /   \
           2     13


Output:
 The root of a Greater Tree like this:
             18
            /   \
          20     13
```

## 2. Implementation

**(1) Recursion**

思路：首先处理right children， 然后当前的node，最后才是leftChildren，维护一个变量sum记录当前所得到的和。

```java
class Solution {
    public TreeNode convertBST(TreeNode root) {
        getSum(root, 0);
        return root;
    }

    public int getSum(TreeNode node, int sum) {
        if (node == null) {
            return sum;
        }

        int rightSum = getSum(node.right, sum);
        node.val += rightSum;
        int leftSum = getSum(node.left, node.val);
        return leftSum;
    }
}
```

**(2) Iteration**

思路：迭代的做法和inorder traversal很像，不同在于我们先从right children遍历，然后是当前的node, 最后才是left children，和inorder traversal正好相反

```java
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        int sum = 0;
        TreeNode curNode = root;

        while (curNode != null || !stack.isEmpty()) {
            if (curNode != null) {
                stack.push(curNode);
                curNode = curNode.right;
            }
            else {
                curNode = stack.pop();
                curNode.val += sum;
                sum = curNode.val;
                curNode = curNode.left;
            }
        }
        return root;
    }
}
```

## 3. Time & Space Complexity

Recursion: 时间复杂度:O(n), 空间复杂度:O(h), h为树的高度

Iteration: 时间复杂度: O(n), 空间复杂度: O(n)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/my-algorithm-summary/data-structure/tree/538-convert-bst-to-greater-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.