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.

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 : {5,2,13}
              5
            /   \
           2     13
Output : {18,20,13}
             18
            /   \
          20     13


Input : {5,3,15}
              5
            /   \
           3     15
Output : {20,23,15}
             20
            /   \
          23     15

Analyzation

Recursion

This problem follows Right -> Root -> Left pattern.

Firstly update the right tree, then add the right subtree’s val to root, and finally add everything to the left subtree.

The Code

class Solution:
    """
    @param root: the root of binary tree
    @return: the new root
    """
    def convertBST(self, root):
        # write your code here
        self.sum = 0
        self.dfs(root)
        return root
    
    def dfs(self, root):
        if root is None:
            return
        
        # Right -> Root -> Left
        if root.right:
            self.dfs(root.right)
        
        # Right + Root
        self.sum += root.val
        root.val = self.sum
        
        # Right + Root + Left
        if root.left:
            self.dfs(root.left)

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).