Formatted question description:

538. Convert BST to Greater Tree




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.


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

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


First obtain the inorder traversal of the binary search tree. The inorder traversal contains all the nodes of the binary search tree with the nodes sorted according to their values.

Loop over the inorder traversal backward, with the last node (the original node in the binary search tree with the greatest value) skipped. For each node, obtain its next node in the inorder traversal (here “next” is in the forward direction), and add its next node’s value to the value of itself. After the operation, the node’s value is changed to the original value plus sum of all values greater than the original value in binary search tree.

Finally, return the root.

  • public class Convert_BST_to_Greater_Tree {
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
        class Solution {
            int sum = 0;
            public TreeNode convertBST(TreeNode root) {
                if (root == null) {
                    return null;
                sum += root.val;
                root.val = sum;
                return root;
  • // OJ:
    // Time: O(N)
    // Space: O(H)
    class Solution {
        int sum = 0;
        TreeNode* convertBST(TreeNode* root) {
            if (!root) return nullptr;
            root->val = (sum += root->val);
            return root;
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution(object):
      def __init__(self):
        self.lSum = 0
      def convertBST(self, root):
        :type root: TreeNode
        :rtype: TreeNode
        if not root:
          return None
        self.lSum += root.val
        root.val = self.lSum
        return root

All Problems

All Solutions